Categories
interview

3Sum – Java

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;
 }
}