[2018-Interview] 3Sum

Original question: https://leetcode.com/problems/3sum/description/

My answer:

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        Set<List<Integer>> resultSet = new HashSet<List<Integer>>();
        if (nums == null || nums.length < 3) {
            return result;
        }
        Arrays.sort(nums);
        for (int i = 0; i <= nums.length - 3; i ++) {
            List<List<Integer>> twoSum = twoSum(nums, i);
            if (twoSum.isEmpty()) {
                continue;
            }
            for (List<Integer> twoSumSingleResult : twoSum) {
                twoSumSingleResult.add(0, nums[i]);
                Collections.sort(twoSumSingleResult);
                resultSet.add(twoSumSingleResult);
            }
        }
        result.addAll(resultSet);
        return result;
    }
    
    private List<List<Integer>> twoSum(int[] nums, int startIndex) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        int nextIndex = startIndex + 1;
        int target = -1 * nums[startIndex];
        // HashMap<Integer, Integer> numCount = new HashMap<Integer, Integer>();
        // for (int i = nextIndex; i < nums.length ; i ++) {
        //     Integer count = numCount.getOrDefault(nums[i], 0);
        //     count += 1;
        //     numCount.put(nums[i], count);
        // }
        // for (int i = nextIndex; i < nums.length ; i ++) {
        //     if (numCount.containsKey(target - nums[i]) && numCount.get(target - nums[i]) > 0) {
        //         if (numCount.get(target - nums[i]) == 1 && (target - nums[i]) == nums[i]) {
        //             // avoid the case where sum of itself can be matched to target
        //             continue;
        //         }
        //         Integer count = numCount.get(target - nums[i]);
        //         ArrayList<Integer> singleResult = new ArrayList<Integer>();
        //         singleResult.add(nums[i]);
        //         singleResult.add(target - nums[i]);
        //         result.add(singleResult);
        //         count --;
        //     }
        // }
        int l = nextIndex;
        int r = nums.length - 1;
        while (l < r) {
            if (nums[l] + nums[r] == target) {
                ArrayList<Integer> singleResult = new ArrayList<Integer>();
                singleResult.add(nums[l]);
                singleResult.add(nums[r]);
                result.add(singleResult);
                l ++;
                r --;
                // important: skip the same element
                while(l<r&&nums[l]==nums[l-1])  
                    l++; 
                while(l<r&&nums[r]==nums[r+1])  
                    r--;
            } else if (nums[l] + nums[r] < target) {
                l ++;
            } else if (nums[l] + nums[r] > target) {
                r --;
            }
        }
        return result;
    }
}