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

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

时间:2024-11-06 13:15:26浏览次数:5  
标签: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

相关文章

  • 使用platformio平台Arduino开发ESP32-C2
    使用platformio平台Arduino开发ESP32-C2有两种方法,推荐方法二。方法一:安装vscode后安装platformio插件(参考:YourGatewaytoEmbeddedSoftwareDevelopmentExcellence·PlatformIO安装时,需要可靠的网络链接。使用platformio创建一个esp32-c3项目(platformio平台默认......
  • 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报文的转发路由器通过对路......