Leetcode 15: 3Sum

题目

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] ]

分析

这道题目是求三个数组之和为0，分两种情况，一种是三个数字全是0，一种是三个数字有正有负才成立，
当前数组是无序的，我们可以考虑对数组排序；
首先可以通过三层循环嵌套的暴力方式解决，时间复杂度为O(n^3)，这里不做讨论；
通过分析，我们可以将第一个数字的相反数设为目标数target，后面的两个数字之和只要等于target就成立，反之不成立；
遍历这个有序数组，取出target，遍历长度为len-2，因为要留下两个数字和target相加，在遍历过程中，我们需要对当前数字进行处理，如果大于0，说明以后的数字都是大于0的，不会出现三数之和等于0的情况，直接跳出返回list，从第二个数字开始，如果之前出现过，需要跳过重复数字；
设置左右两个指针，左指针为当前数字的下一个数字，右指针为数组最后一个数字，遍历截取的数组，如果左右两个指针之和等于target，就代表寻找到了一组，继续寻找下一组，左指针加一，右指针减一，左右指针也需要跳过重复数字，当左指针大于等于右指针时，跳出当前循环。

代码

public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> list = new ArrayList<>();
        int left,right;//左右指针
        for (int i = 0; i < nums.length - 2; i++) {
            //如果数字大于0，直接跳出循环
            if (nums[i] > 0) {
                break;
            }
             //数字重复处理
            if (i > 0 && nums[i - 1] == nums[i]) {
                continue;
            }
            left= i + 1;
            right = nums.length - 1;
            while (left < right) {
                if (nums[left] + nums[right] == -nums[i]) {//满足条件
                    List<Integer> l = new ArrayList<>();
                    l.add(nums[i]);
                    l.add(nums[left]);
                    l.add(nums[right]);
                    list.add(l);
                    left++;
                    right--;
                    //左指针重复处理
                    while (left< right&& nums[left] == nums[left- 1]) {
                        left++;
                    }
                    //右指针重复处理
                    while (left< right&& nums[right] == nums[right+ 1]) {
                        right--;
                    }
                } else if (nums[left] + nums[right] > -nums[i]) {
                    right-= 1;
                } else {
                    left+= 1;
                }
            }
        }
        return list;
    }