LeetCode 15. 3Sum

Leetcode : 3sum
Diffculty：Medium

题目：

给定一个n个整数的数组 nums , 其中存在三个元素组成的三元组 (a,b,c)，使得a+b+c=0。找出所有这样的三元组

注意：

1） 三元组结果必须是非降序的，即(a,b,c)的三元组 a<=b<=c
2） 不能包含重复的三元组，即，需要对结果去重。

解决思路：

这其实和Two Sum 的思路类似，可以转化为 b+c=target 这个target就是-a，这样就使得a+b+c=0。所以可以定位一个点a，然后移动两个指针分别为b和c。寻找答案。

时间复杂度：O(N^2)

具体思路为：
1）首先将数组排序
2）for循环遍历数组，取得第一个元素 a，然后left=a+1, right=num.length-1。
3） int temp = num[a] + num[left] + num[right]。
如果 temp=0 则找到结果，两个指针向中间收缩。 left++; right--
如果 temp<0 则结果偏小，left指针右移 left++;
如果 temp>0 则结果偏大，right指针左移 right--;
4）对结果的去重，要充分利用数组的有序性。
例如：
在找第一个元素时 if(i>0 && nums[i] == nums[i-1]) 可以判断该元素是不是和上一次迭代相同，相同则跳过
在对left 和 right 指针移动时，while(left < right && nums[left]==list.get(1)) left++; 循环校验，判断是不是和已经计算过的元素值相同，相同则继续移动。

下面上代码：

public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if(nums == null){
            return result;
        }

        Arrays.sort(nums);
        int left,right,temp;
        for(int i=0; i<nums.length; i++){
            if(nums[i] > 0){  // 如果大于0则不需要遍历了。后面的都大于0
                break;
            }
            // 跳过i重复的元素，还是利用的序列的有序性质
            if(i>0 && nums[i] == nums[i-1]){
                continue;
            }
            left = i+1;
            right = nums.length - 1;
            while(left<right){
                temp = nums[i] + nums[left] + nums[right];
                if(temp == 0){
                    List<Integer> list = Arrays.asList(nums[i],nums[left],nums[right]);
                    result.add(list);

                    // 循环校验。由于数组已经有序，所以这个操作可以跳过那些重复元素
                    // 从而可以对结果去重
                    while(left < right && nums[left]==list.get(1)) left++;
                    while(left < right && nums[right]==list.get(2)) right--;
                }else if(temp > 0){
                    right--;
                }else{
                    left++;
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{-2,0,0,2,2};
        int[] arr_2 = new int[]{-1,0,1,2,-1,-4};
        System.out.println(GsonUtil.toJson(threeSum(arr)));
        System.out.println(GsonUtil.toJson(threeSum(arr_2)));
    }

结果为：

[[-2,0,2]]
[[-1,-1,2],[-1,0,1]]

leetcode 运行时间 超过 65.10%
（这个方法还只是很一般的解法，大神很多啊）

---

附参考资料：
CSDN:Three-Sum 三个数的和