Categories

# 3Sum

## Time O(n2) & Memory O(1)

```class Solution {
public List < List < Integer >> threeSum(int[] nums) {
int n = nums.length;
List < List < Integer >> list = new ArrayList < List < Integer >> ();
if(nums == null || nums.length<3)
return list;
Arrays.sort(nums);
int left, right;
for (int i = 0; i < n - 2; i++) {
if(i > 0 && nums[i] == nums[i-1])
continue;
left = i + 1;
right = n - 1;
while (left < right) {
if (nums[left] + nums[right] + nums[i] == 0) {
List < Integer > temp = new ArrayList < Integer > ();
left++;
right--;
while (left< right && nums[left] == nums[left - 1]) {
left++;
}
while (left< right && nums[right] == nums[right + 1]) {
right--;
}
} else if (nums[left] + nums[right] + nums[i]  > 0) {
right--;
} else
left++;
}
}
return list;
}
}```

## Javascript ES6

``````const get3Sum = (arr) => {
const results = [];
arr.sort((a, b) => a - b);
for (let i = 0; (i < arr.length - 2) && (arr[i] <= 0); i++) {
if (i === 0 || arr[i] !== arr[i - 1]) {
getPair(arr, i, results);
}
}
return results;
};

const getPair = (arr, i, results) => {
let left = i + 1;
let right = arr.length - 1;
while (left < right) {
const sum = arr[i] + arr[left] + arr[right];
if (sum === 0) {
results.push([arr[i], arr[left++], arr[right--]]);
while (left < right && arr[left - 1] == arr[left]) {
left++;
}
} else if (sum < 0) {
left++;
} else if (sum > 0) {
right--;
}
}
};

console.log(get3Sum([-1, 0, 1, 2, -1, -4]));
// [[-1 , 0, 1], [-1, -1, 2]]``````

Demo