【每日一题Day260】LC15三数之和 | 排序 + 双指针

三数之和【LC15】

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

**注意：**答案中不可以包含重复的三元组。

排序+双指针

思路
- 首先对数组进行排序，然后遍历数组，在确定nums[i]的情况下，在数组nums[i+1,n-1]中使双指针法（前后指针），确定另外两个元素，判断这三个元素之和sum与target的大小：
  - 如果 $s u m > t a r g e t$ ，左移左指针，使sum减小
  - 如果 $s u m < t a r g e t$ ，右移右指针，使sum增大
  - 如果 $s u m == t a r g e t$ ，添加三元组至结果集
- 去重：
  - 在找到符合条件的三元组后，移动指针r、l跳过相同元素，以便过滤掉重复的三元组
  - 如果nums[i]==nums[i-1]， $n u m s [i]$ 的三元组是 $n u m s [i - 1]$ 的子集，需要跳过
  - 在遇到不符合条件的左右边界时也可以移动双指针去重，但是由于根据sum和target的大小关系，双指针也会被移动，所以此时是否去重不是必须的
实现
1. 首先将数组排序；
2. 然后有一层for循环， $i$ 从下表0的地方开始，同时定义下标left在i+1位置上，定义下标right在数组末尾的位置上
3. 如果nums[i]>0,不可能存在三元组，直接退出循环，返回结果集
4. 去重：如果(i > 0 && nums[i] == nums[i - 1])， $n u m s [i]$ 的三元组是 $n u m s [i - 1]$ 的子集，需要跳过
5. 移动left和right
  - 如果nums[i] + nums[left] + nums[right] > 0,说明right下标应该向左移动
    
    去重：while (left < right && nums[right] == nums[right + 1]) right--;【非必须】
  - 如果nums[i] + nums[left] + nums[right] < 0,说明left下标应该向右移动
    
    去重： while (left < right && nums[left] == nums[left - 1]) left++;【非必须】
  - 如果nums[i] + nums[left] + nums[right] == 0,说明找到了三元组，双指针同时收缩，right--；left++
    
    去重： while (right > left && nums[right] == nums[right - 1]) right--;
    while (right > left && nums[left] == nums[left + 1]) left++;
```
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++){
            if (nums[i] > 0){
                return res;
            }
            if (i > 0 && nums[i] == nums[i-1] ){
                continue;
            }
            int left = i + 1;
            int right = nums.length - 1;
            while (left < right){
                int sum = nums[i] + nums[left] + nums[right];
                if (sum > 0){
                    right--;
                    // 非必须
                    while(left < right && nums[right] == nums[right+1]){
                        right--;
                    }
                }else if (sum < 0){
                    // 非必须
                    left++;
                    while (left < right && nums[left-1] == nums[left]){
                        left++;
                    }
                }else{
                    res.add(Arrays.asList(nums[i],nums[left],nums[right]));
                    while(left < right && nums[right] == nums[right-1]){
                        right--;
                    }
                    while (left < right && nums[left+1] == nums[left]){
                        left++;
                    }
                    right--;
                    left++;
                }
            }
        }
        return res;
    }
}
```
```
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        int len = nums.length;
        int i  = 0;
        while (i < len - 2){
            twoSum(nums,i,res);
            int temp = nums[i];
            while (i < len && temp == nums[i]){
                i++;
            }
        }
        return res;
    }
    public void twoSum(int[] numbers, int i, List<List<Integer>> res ) {
        int len = numbers.length;
        int left = i + 1;
        int right = len - 1;
        while(left < right){
            if ( numbers[i] + numbers[left] + numbers[right] == 0){
                res.add(Arrays.asList(numbers[i],numbers[left],numbers[right]));
                int temp = numbers[left];
                while (numbers[left] == temp && left < right){
                    left++;
                }
            }else if(numbers[i] + numbers[left] + numbers[right] > 0){
                right--;
            }else {
                left++;
            }
        }
    }
}
```
  - 复杂度
    - 时间复杂度： $O(nlogn+n^2)$ ，其中 n是数组的长度。排序所需的时间复杂度一般为 $O (n l o g n)$ ，查找三元组的时间复杂度为 $O(n^2)$ ，因此时间复杂度为 $O(n^2)$
    - 空间复杂度： $O (1)$