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

Note:The solution set must not contain duplicate triplets.

``````For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
``````

Thoughts:

a + b + c =0 <=> a + b = -c

Traverse each element : a target of two sum. Search direction should be consistent with the direction of traverse order(avoid duplicates).

[code 1: using map]: O(n^2) + Extra Space (HashMap/ unordered_map) : https://leetcode.com/problems/3sum/discuss/163934/Efficient-Java-Solution

``````class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) map.put(nums[i], i); // val , last index

for(int i = 0 ; i < nums.length - 2; i++){
for(int j = i + 1; j < nums.length -1; j++){
int target = 0 - nums[i] - nums[j];

if (map.containsKey(target) && map.get(target) > j){
j = map.get(nums[j]); // Taking the last index of j to remove duplicate
}
}
i = map.get(nums[i]); // Taking the last index of i to remove duplicate
}

return res;
}
}
``````
``````class Solution {
public List<List<Integer>> threeSum(int[] nums) {
if(nums == null || nums.length == 0) return new ArrayList<>();
int n = nums.length;
List<List<Integer>> res = new ArrayList<>(); // 1
Map<Integer, Integer> map = new HashMap<>();
for(int i = 0 ; i < n; i++){
map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
}
// cross product
for(int i : map.keySet()){
for(int j: map.keySet()){
if(i > j || (i == j && map.get(i) == 1)) // imposing j>= i
continue;

int k = -i - j;
if(map.containsKey(k)){
if(j > k) continue; // imposing k >= j order
int size = map.get(k);
if(((k == j)&& size == 1) ||            // since k >= j >= i
((k == i && i == j) && size == 2)) // deduplication
continue;

}
}
}

return res;
}
}
``````

Python

``````class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
# time O(n^2), space O(1)
if not nums: return []

n, m = len(nums), collections.defaultdict(int) # {x:nums.count(x) for x in nums} #dict(collections.Counter(nums))
for num in nums: m[num]+=1

return [[i, j, -i-j] for i in m.keys()
for j in m.keys() if (j > i or (i == j and m[i] > 1))
and ((-i -j) in m )
and ((-i-j)>= j)
and (m[(-i-j)] > 2 or m[(-i-j)] == 1 and (-i-j)!=j or m[(-i-j)] == 2 and ((-i-j)!=i or (-i-j)!=j))]
``````

[code 2: two pointer]: O(n^2) without extra space (ordered_map)

``````class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
int n = nums.length;
for(int i = 0; i < n - 2;  i++){
if(i == 0 || nums[i] != nums[i-1]){
int j = i + 1, k = n - 1;
while(j < k){
if(nums[i] + nums[j] + nums[k] == 0){
// deduplication
while(j < k && nums[j] == nums[j + 1]) j ++;
while(j < k && nums[k] == nums[k - 1]) k --;
j++; k--;
}
else if(nums[i] + nums[j] + nums[k] < 0) j++;
else k --;
}
}
}

return res;
}
}
``````

Variation: Expand sum to be 0 as in general case

``````class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums, int target) {
int len = nums.size();
if (len < 3) return answer;

// sort the vector
sort(nums.begin(), nums.end());

for(int i = 0; i < len; i++){

int left = i + 1, right = len - 1, twoSumTarget = target - nums[i]; // THE ONLY DIFFERENCE!

// treat as two sum using two pointers
while(left < right){
// speed up two sum runtime by removing two sum search for duplicated target value
// while(i > 0 && nums[i] == nums[i-1]) i++;
// alternatively, you can write :
if(i>0 && nums[i] == nums[i-1]) continue;
//at the beginning of the for loop

int sum = nums[left] + nums[right];
if( sum == twoSumTarget ){
// speed up two sum search runtime by removing duplicates
left++;
right--;
while(left < right && nums[left] == nums[left-1]) left++; // you may not need "left<right"
//here in C++

while(left < right && nums[right] == nums[right+1])right--; // you may not need "left<right"
//here in C++

}
else if (sum < twoSumTarget ){
left ++;
}
else{
right--;
}

}

}