# 3 Sum

[LintCode 3 Sum](http://www.lintcode.com/en/problem/3sum/)

## Question

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.

**Notice**

Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)

The solution set must not contain duplicate triplets.

## Analysis

考虑non-descending，先sort数组，其次考虑去除duplicate；\
类似2sum，可以利用two pointers，不断移动left 和 right 指针，直到找到目标，或者两指针相遇

一重循环i遍历数组，作为a，其余两个指针left和right分别对应b，c。这样最终时间复杂度为 O(n^2)。

```
> Time Complexity O(n^2)
> Space Complexity O(1)
```

<https://leetcode.com/problems/3sum/discuss/169885/Python-or-tm>

**固定区间的Two-Pointer**&#x20;

大概思路是外围for-loop一遍数组，然后在*每次迭代的时候，设置`[l, r]`的区间*，区间范围为`l , r = i + 1, len(nums) - 1`, 这样比对的数就有3个，分别是`nums[i], nums[l] 和 nums[r]`.

最终要达到的效果是:

`nums[l] + nums[r] == -nums[i]`

这道题一定要**记住去重**，不仅仅是区间的`l`和`r`要去重，外围的`i`也需要去重。去重的方法如下:

`i`去重：`if i == 0 or nums[i] > nums[i-1]:`

`l`去重：`while l < r and nums[l] == nums[l-1]: l += 1`

`r`去重：`while l < r and nums[r] == nums[r+1]: r -= 1`

## Solution

Two Pointers - (40ms, 97.77%)

```java
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums == null || nums.length < 3) {
            return res;
        }
        Arrays.sort(nums);

        for (int i = 0; i < nums.length - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int j = i + 1;
            int k = nums.length - 1;
            int target = 0 - nums[i];

            while (j < k) {
                if (nums[j] + nums[k] > target) {
                    k--;
                } else if (nums[j] + nums[k] < target) {
                    j++;
                } else {
                    res.add(Arrays.asList(nums[i], nums[j], nums[k]));

                    j++;
                    k--;

                    // skip duplicates
                    while (j < k && nums[j] == nums[j - 1]) {
                        j++;
                    }
                    while (j < k && nums[k] == nums[k + 1]) {
                        k--;
                    }
                }
            }
        }
        return res;
    }
}
```

Another Two Pointer

```java
public class Solution {
    /**
     * @param numbers : Give an array numbers of n integer
     * @return : Find all unique triplets in the array which gives the sum of zero.
     */
    public ArrayList<ArrayList<Integer>> threeSum(int[] numbers) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        if (numbers == null || numbers.length < 3) {
            return result;
        }
        Arrays.sort(numbers);

        for (int i = 0; i < numbers.length - 2; i++) {
            if (i > 0 && numbers[i] == numbers[i - 1]) {
                continue;
            }
            int left = i + 1;
            int right = numbers.length - 1;

            while (left < right) {
                int sum = numbers[i] + numbers[left] + numbers[right];
                if (sum == 0) {
                    ArrayList<Integer> tmp = new ArrayList<Integer>();
                    tmp.add(numbers[i]);
                    tmp.add(numbers[left]);
                    tmp.add(numbers[right]);
                    result.add(tmp);
                    left++;
                    right--;
                    while (left < right && numbers[left] == numbers[left - 1]) {
                        left++;
                    }
                    while (left < right && numbers[right] == numbers[right + 1]) {
                        right--;
                    }
                } else if (sum < 0) {
                    left++;
                } else {
                    right--;
                }

            }
        }
        return result;
    }
}
```

## Reference

* [九章算法题解 3 Sum](http://www.jiuzhang.com/solutions/3sum/)
* [MIT Paper Ilya Baran: Subquadratic Algorithms for 3SUM](http://www.mit.edu/~ibaran/papers/3sum.pdf)