首页 > 其他分享 >7.《双指针篇》---⑦三数之和(中等偏难)

7.《双指针篇》---⑦三数之和(中等偏难)

时间:2024-11-06 13:15:26浏览次数:3  
标签:right target nums int 三数 sum --- 偏难 left

题目传送门 

方法一:双指针

1.新建一个顺序表用来返回结果。并排序数组。

2.for循环 i 从第一个数组元素遍历到倒数第三个数。

3.如果遍历过程中有值大于0的则break; 

4.定义左右指针,以及target。int left = i + 1, right = n - 1; int target = -nums[i];

5.类似两数之和。比较int sum = nums[l] + nums[r] 与 target的大小

注意:

1.不能返回重复的数组。因此我们还需要排除重复的。

2.排序之后。在sum = target的时候。我们进行 left 和 right的排重。

3.在 i++ 之后我们进行 num[i] 这个元素的排重。

注意:

排重的时候双指针排重记得 left < right。并且num【i】排重的时候注意 i<n-1。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();
        Arrays.sort(nums);
        int n = nums.length-1;

        for(int i = 0; i < n-1; ){
            if(nums[i] > 0){
                break;
            }
            int left = i + 1;
            int right = n;
            int target = -nums[i];

            while(left < right){
                int sum = nums[left] + nums[right];
                if(sum == target){
                    ret.add(new ArrayList<Integer>(Arrays.asList(nums[i],nums[left],nums[right])));
                    left++;
                    right--;
                    while(left < right && nums[left] == nums[left-1]){
                        left++;
                    }
                    while(left < right && nums[right] == nums[right+1]){
                        right--;
                    }

                }else if(sum < target){
                    left++;
                }else{
                    right--;
                }
            }
            i++;
            while(i<n-1 && nums[i] == nums[i-1]){
                i++;
            }

        }
        return ret;
    }
}

 复杂度分析

标签:right,target,nums,int,三数,sum,---,偏难,left
From: https://blog.csdn.net/m0_73456341/article/details/143567898

相关文章

  • Dev-C++调试提示“项目没有调试信息,您想打开项目调试选项并重新生成吗”解决方法
    在下载完DEV-C++以后进行第一次调试时,系统弹出以上窗口,点击“Yes”按钮后编译器出现秒退的情况。一、打开“产品调试信息”菜单栏→工具→编译选项→代码生成/优化→连接器→产生调试信息→更改为“Yes”。打开“产品调试信息”后,代码行变为蓝色,但是调试栏没有显示信息......
  • 使用platformio平台Arduino开发ESP32-C2
    使用platformio平台Arduino开发ESP32-C2有两种方法,推荐方法二。方法一:安装vscode后安装platformio插件(参考:YourGatewaytoEmbeddedSoftwareDevelopmentExcellence·PlatformIO安装时,需要可靠的网络链接。使用platformio创建一个esp32-c3项目(platformio平台默认......
  • Codeforces 1847 A-F
    题面ABCDEF难度:红橙黄蓝紫紫题解B题目大意:找到一组分割方法,使得\(\sum_{i=1}^k(\text{&}_{j=l_i}^{r_i}a_j)\)取得最小值时使\(k\)最大,输出\(k\)。其中\(\text{&}\)表示按位与操作。题目分析:&01000101不难发现,因为\(a\in......
  • GS-Blur数据集:首个基于3D场景合成的156,209对多样化真实感模糊图像数据集。
    2024-10-31,由韩国首尔国立大学的研究团队创建的GS-Blur数据集,通过3D场景重建和相机视角移动合成了多样化的真实感模糊图像,为图像去模糊领域提供了一个大规模、高覆盖度的新工具,显著提升了去模糊算法在真实世界场景中的泛化能力。数据集地址:GS-Blur|图像去模糊数据集|图像处理......
  • 小白反思 -- 长记性长记性长记性
    2024年11月6日踩过的坑要长记性1.正确使用多个python环境一个电脑可能不止装了一个python,可能有标准版的python,可能有embeddedpython,所以,系统会默认使用某一个python,你也不知道是哪一个。如果你想在某个python环境里安装某个库时,使用pipinstallXXX装好了之后,引用的时候......
  • CSP/信奥赛C++完整学习规划(价值2万的csp-j完整课程体系)
    CSP/信奥赛C++课程完整学习视频一站式掌握信奥赛知识冲刺信奥赛拿奖课程购买后永久学习,不受限制!阶段一:《信奥赛C++语法基础》课程目标:轻松入门C++语法课程链接:https://edu.csdn.net/course/detail/39557阶段二:《信奥赛C++语法进阶》课程目标:快速进阶C++语法......
  • 笔记--(网络1)、网络参考模型,数值转换
    常见术语术语说明数据载荷最终想要传递的信息报文网络重交换与传输的数据单元头部在数据载荷的前面添加的信息段尾部在数据载荷的后面添加信息段封装对数据载荷添加头部和尾部,形成新的报文的过程解封装去掉报文的头部和尾部,获取数据载荷的过程网关提供协议转换、路由选择、......
  • 笔记--(网络4)、路由
    路由条目包含以下信息目的网络:目的网段的网络号掩码:目的网段的掩码出接口:数据包从本路由器发出的接口下一跳:到达目的网段的下一跳的设备地址路由表路由器通过各种方式发现路由路由器选择最优的路由条目放入路由表中路由表指导设备对IP报文的转发路由器通过对路......
  • 【华为笔试-3】HJ20 密码验证合格程序
    HJ20密码验证程序输入:021Abc9000021Abc9Abc1021ABC9000021$bc9000输出:OKNGNGOK注:输入结束后有中止结束标志EOF【这个原题给的时候无说明,自己跑他的用例和看论坛看出来的】题解:要点有三个,分别是:长度超过八位、包含三种以上、和公共子字符串,以及输入输出输入输......
  • LiteOS学习笔记[01]-weharmonyos-基础知识
    双向链表为什么LOS_ListHeadInsert的实现是从头部节点的后面也就是第二个节点的位置插入新节点,而不是直接将头部节点更新为插入的节点?头部节点的作用:在双向链表中,头部节点(通常称为头结点或哑结点)通常不存储实际的数据,而是作为链表的起始点和操作的辅助节点。它使得链表的操作......