[Java知识库]LeetCode-100题(Hot) 15. 三数之和 [Java实现]

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

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

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

第一眼想到 O(n^3) 暴力求解，但是解决不了重复的问题。开始优化：

不妨设 a < b < c 那么在关于 b c 的二三重遍历中始终存在 b < c，且当b的值增加时只可能在原c的左侧存在一c'（c' < c）使得 -a=b+c 继续成立，符合双指针法的思想。又考虑到形如 [ -1，0，0，0，1] 的情况，所以可以增加判断条件当当前遍历项的值=上一次遍历项的值时，跳过本次遍历。综上 O(n^3) 的原算法可优化成 O(nlogn)（排序） + O(n^2)（双指针法）= O(n^2)。代码如下：

    public List<List<Integer>> threeSum(int[] nums) {
        int length = nums.length;
        if (length < 3) {
            return new ArrayList<>();
        }
        Arrays.sort(nums);
        List<List<Integer>> list = new LinkedList<>();
        for (int first = 0; first < length; first ++) {
            if (first > 0 && nums[first] == nums[first-1]) {
                continue;
            }
            int third = length-1;
            int value = -nums[first];
            for (int second = first+1; second < length; second ++) {
                if (second > first+1 && nums[second] == nums[second-1]) {
                    continue;
                }
                while (second < third && nums[second]+nums[third] > value) {
                    third --;
                }
                if (second == third) break;
                if (nums[second]+nums[third] == value) {
                    list.add(Arrays.asList(nums[first], nums[second], nums[third]));
                }
            }
        }
        return list;
    }