【LeetCode100】--- 6.三叔之和【思维导图---复习回顾】

题目传送门

方法一：使用双指针+排序

先排重num【i】版本

由于当前还没有计算过 nums[i] 
如nums【-4，-1，-1,0,1,2】
若直接排重就会错过如 [-1,-1,2] 这样的结果。
因此当前排重只需要

if(i > 0 && nums[i] == nums[i-1]){
    continue;
}

这样就不会错过
如 [-1,-1,2] 这样的结果。因为前置判断后会计算（重复元素的前列）
当num[i] 等于第一个 -1 的结果

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

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

                while(left < right){
                if(nums[left] + nums[right] == target){
                    ret.add(Arrays.asList(nums[i],nums[left],nums[right]));
                    while(left < right && nums[left] == nums[left+1] ) {
                        left++;
                    }
                     while(left < right && nums[right] == nums[right-1]){
                        right--;
                    }
                    left++;
                    right--;
                }else if(nums[left] + nums[right] < target){
                    left++;
                }else{
                    right--;
                }
            }
        }
        return ret;
    }
}

算法思维导图 

后排重nums【i】版本

如nums【-4，-1，-1,0,1,2】
由于此时已经把当前 num[i] （重复元素的前列）计算过了
此时就已经加上如 [-1,-1,2] 这样的结果
因此直接while循环排重 num[i] 最后由于for循环还有i++
成功排重 nums【i】

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

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

            while(left < right){
                if(nums[left] + nums[right] == target){
                    ret.add(Arrays.asList(nums[i],nums[left],nums[right]));
                    while(left < right && nums[left] == nums[left+1] ) {
                        left++;
                    }
                     while(left < right && nums[right] == nums[right-1]){
                        right--;
                    }
                    left++;
                    right--;
                }else if(nums[left] + nums[right] < target){
                    left++;
                }else{
                    right--;
                }
            }
            while(i < n-3 && nums[i] == nums[i+1]){
                i++;
            }
        }
        return ret;
    }
}

算法思维导图

复杂度分析： 

时间复杂度：O(n log n)

• 排序：O(n log n)
• 外层循环 + 双指针扫描：O(n) × O(n) = O(n²)
   

空间复杂度（O(log n)）

该算法的空间复杂度为 O(log n)，主要来源于排序过程中的递归调用栈空间。结果列表的空间通常不计入复杂度，因为它取决于输入的具体情况（解的数量），而非算法本身的实现。