Categories
interview

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 > ();
     temp.add(nums[i]);
     temp.add(nums[left]);
     temp.add(nums[right]);
     list.add(temp);
     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