JunyiCode
3/22/2020 - 3:35 AM

## 15. 3Sum

2 pointers

``````/*
tricky part:
1. skip equal elements to avoid duplicate
1.1 first element duplicates
1.2 second and third element duplicate

The idea is to sort an input array and then run through all indices of a possible first element of a triplet.
For each possible first element we make a standard bi-directional 2Sum sweep of the remaining part of the array.
Also we want to skip equal elements to avoid duplicates in the answer without making a set or smth like that.
*/

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

for(int i = 0; i < nums.length - 2; i++) {
if(nums[i] > 0)
break;   //optimization
if(i == 0 || (i > 0 && nums[i] != nums[i - 1])) {
int low = i + 1, high = nums.length - 1, target = 0 - nums[i];
while(low < high) {
if(nums[low] + nums[high] == target) {
while(low < high && nums[low] == nums[low + 1])   low++;
while(low < high && nums[high] == nums[high - 1]) high--;
low++;
high--;
} else if(nums[low] + nums[high] < target) {
low++;
} else {
high--;
}
}
}
}
return res;
}

// public int[] twoSum(int[] nums, int target) {
//     int[] res = new int[2];
//     Map<Integer, Integer> map = new HashMap<>();

//     for(int i = 0; i < nums.length; i++) {
//         if(map.containsKey(target - nums[i])) {
//             res[0] = map.get(target - nums[i]);
//             res[1] = i;
//             return res;
//         }
//         map.put(nums[i], i);
//     }

//     return res;
// }
}``````