这个题目难度中等，楼主的情况是自己做了一遍，去重不完全，结果老是重复，后来放弃了，开始看大牛们的解题思路，根据他们的解题思路，自己又做了好几天才跑过所有的case，这道题真是个拦路虎啊。

题目

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]

题目其实超级简单

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

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

1. 开始最原始的思路肯定是循环三次数组，然后求和，记得去重，但这样的问题是时间复杂度是O(n^3),再加上去重，系统应该不会接受这个答案。

2. 降低时间复杂度到 n^2

   楼主想法，先排序，取一遍所有的数字和他的反数（0-nums[i]）,同时第二遍循环是得出所有数字和位置大于他数字的 2sum。 再用反数作为key， 查找所有的 b 和 c，这个做的问题是，重复太多，没想出太好的去重办法。

失败的code。。。

3. 大家普遍认可的思路，简单来说就是 双指针 + 去重。

• 先排序

• 取第 i个元素，判断这个数是不是> 0 , 因为排过序，如果第一个直接> 0 就没有必要继续了， 同时还要判断这个数和前一个数是不是重复，重复的话，可以直接跳过

• 得到 i 元素的反数 0 - nums[i], 以及i元素后面的首位元素位置 beg = i + 1， end = nums.length - 1

• 然后就是 看 nums[beg] + nums[end] 的关系了，大于target 就需要把end 向左移动一位，减小数值，如果小于target 就需要把beg 向右移动一位，增大数值，知道左右指针重逢。 其中注意移动过程中 去重，遇到和前一个数字重复的情况，需要继续移动。

代码

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> threeSumList = new ArrayList<>();

        //sort nums first
        Arrays.sort(nums);
        
        for(int i = 0; i <nums.length; i++){
            
            //no valid triplets exists
            if( nums[i] > 0) break;
            
            //Duplicate
            if (i>0&&nums[i]==nums[i-1]) continue;  
            
            int target = 0 - nums[i];            
            int beg = i + 1;
            int end = nums.length - 1 ;
           
            while (beg < end){
                // if the sum is bigger, end should shift to left
                if(nums[beg] + nums[end] > target) end--; 
            
                // if the sum is smaller, beg should shift to right
                if(beg < end && nums[beg] + nums[end] < target) beg++;
            
                if(beg < end && nums[beg] + nums[end] == target){
                    //Duplicate
                    while (beg < end && nums[beg] == nums[beg + 1]) beg++;
                    while (beg < end && nums[end] == nums[end - 1]) end--;
                    
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[beg]);                
                    list.add(nums[end]);
                
                    threeSumList.add(list);
                
                    end--;
                    beg++;
                }
                
            }
                        
        }
        return threeSumList;
    }
}

时间复杂度是 O(n^2)

image.png

进而，所有sum的衍生题应该都可以用相似的逻辑解决，下面一题是4Sum.

https://www.jianshu.com/p/8c4f2c37f8fe