3 Sum

题目

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

给出一个有n个整数的数组S，在S中找到三个整数a, b, c，找到所有使得a + b + c = 0的三元组。

https://leetcode.com/problems/3sum/description/

样例

For example, given array S = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]

解题思路

这道题，用两个指针 Two Pointers的方式做会比较容易理解，此时的算法时间复杂度是O(n^2)。
要注意的地方有两个。
一是要注意提前给数组排序，用

Arrays.sort();

的方式就可以实现，这个排序是用快速排序的方式，时间复杂度是O(nlogn)；
二是要注意由于题目中专门要求了要unique的结果，所以要排除掉相同的状况。
具体代码如下：

public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        
        for (int i = 0; i < nums.length; i++) {
            // skip the same result
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int left = i + 1, right = nums.length - 1;
            while (left < right) {
                List<Integer> temp = new ArrayList<Integer>();
                if (nums[left] + nums[right] + nums[i] == 0) {
                    temp.add(nums[i]);
                    temp.add(nums[left]);
                    temp.add(nums[right]);
                    res.add(temp);
                    // skip the same result
                    while (left < right && nums[left] == nums[left + 1]) {
                        left++;
                    }
                    // skip the same result
                    while (left < right && nums[right] == nums[right - 1]) {
                        right--;
                    }
                    left++;
                    right--;
                } else if (nums[left] + nums[right] + nums[i] < 0) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return res;
}