15. 3Sum

// sort nums
// if first num is positive, return empty solution set
// only need to lock 1
// as 2 increases, 3 must decrease since (1,2,3) is in numerical order

class Solution {
  public List<List<Integer>> threeSum(int[] nums) {
    ArrayList<List<Integer>> ret = new ArrayList<List<Integer>>();

    if (nums.length < 3) return ret;

    Arrays.sort(nums);

    for(int i = 0; i < nums.length - 2; i++) {

      if(nums[i] > 0) {
        // No more solutions can be found
        return ret;
      }

      if(i > 0 && nums[i-1] == nums[i]) continue; // Skip duplicates

      int j = i + 1;
      int k = nums.length - 1;

      while(j < k) {

        if(j > (i+1) && nums[j-1] == nums[j]) {
          j++; // Skip duplicates
          continue;
        }

        if(k < (nums.length - 1) && nums[k] == nums[k+1]) {
          k--; // Skip duplicates
          continue;
        }

        int sum = nums[i] + nums[j] + nums[k];

        if (sum > 0) {
          k--;
        } else if (sum < 0) {
          j++;
        } else {
          ret.add(Arrays.asList(nums[i], nums[j], nums[k]));
          j++;
          k--;
        }
      }
    }

    return ret;
  }
}