当前位置：首页 > article >正文

leetcode 15. 三数之和

article 2024/9/20 0:03:28

代码：

class Solution {
    public static List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> lists=new ArrayList<>();
        int length=nums.length;
        for(int i=0;i<=length-3;){
            int left=i+1;
            int right=length-1;

            while (left<right){
                if(nums[left]+nums[right]>-nums[i]){
                    right--;
                }else if(nums[left]+nums[right]<-nums[i]){
                    left++;
                }else {
                    //满足条件，将数据保存到二维列表中
                    lists.add(new ArrayList<>(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--;
                    }
                }
            }

            i++;
            while (i<=length-3&&nums[i]==nums[i-1]){
                i++;
            }
        }

        return lists;
    }
}

题解：

我们要在数组中选出相加为 0 的三个数，要选出符合条件的多个数，我们可以尝试采用先排序，利用有序数组的单调性和双指针的方式解决，推荐先看leetcode LCR 179. 查找总价格为目标值的两个商品（优质解法）

首先对于示例，-2.-1，-1，2，4，1，1，1，1,经过排序以后得到 -2.-1，-1，1，1，1.，2，4,1由于此时我们要获取 3 个数，而采用双指针的方式只能探讨两个数的选择，所以我们可以先固定一个数，先用指针 i 指向要固定的数 -1,此时我们只需要在 i 右边的区间内找到两个数，使 nums[ L ] + nums[ R ]= — nums[ i ] 即可

如下图，让指针 L 指向右边区间中最小的数，R 指向右边区间中最大的数，此时 -1+4= 3 > 2,此时得到的数据较大，而 L 指针已经指向了区间中最小的数，所以就要淘汰大的数 4 ，指针 R- -

-2 -1 -1 1 1 1 1 2 4

i L R

当 R- - 以后 -1 +2 = 1 < 2 此时得到的数据较小，而 R 指针已经指向了区间中最大的数，所以就要淘汰小的数 -1 ，指针 L ++

-2 -1 -1 1 1 1 1. 2 4

i L R

当指针 L ++ 以后,-1 + 1 = 0 < 2 此时得到的数据较小,而 R 指针已经指向了区间中最大的数，所以就要淘汰小的数 -1 ，指针 L ++

-2 -1 -1 1 1 1 1. 2 4

i L R

当指针 L ++ 以后,1+1=2=2 ,此时 nums[ i ]，nums[ L ]，nums[ R ]就是一组满足条件的三元组，将该三元组保存到二维列表中，由于我们要找出所有的情况，所以此时还不能返回，要继续寻找

-2 -1 -1 1 1 1 1. 2 4

i L R

让 L++，R- -，此时 L 指向的是 1 和之前一样，由于题目要求不能有重复数据，此时即使 L 指针指向的数据和 R 指针指向的数据满足要求，也是重复的，不需要的数据，所以当 nums[ L ]=nums[ L -1 ] 时，就直接跳过，L++，R 指针也是一样的道理，当 nums[ R ]=nums[ R +1 ] 时,就直接跳过， R- -，这样就能保证我们得到的结果不重复

-2 -1 -1 1 1 1 1. 2 4

i L R

在处理数据重复方面，我们还需要注意一个情况，如图当 i 指针指向 -1 时，就代表要在右边的集合中寻找两个数，两个数相加的和为 1，而 i-1 下标指向的值也是 -1 ，就代表之前已经在右边的区间寻找了相加和为 1 的两个数了，此时再寻找也只会找到同样的数，就会导致数据重复，所以当 nums[ i ]=nums[ i - 1 ] 时，就直接跳过，i++，这样就能保证我们得到的结果不重复

-2 -1 -1 1 1 1 1. 2 4

i-1 i

查看全文

http://www.kler.cn/news/150226.html