# 3 Sum

LintCode 3 Sum

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

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

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

`nums[l] + nums[r] == -nums[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%)

``````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 {

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

``````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>();
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;
}
}
``````