Java structured solution with 2Sum problems as subproblem


  • 0
    A
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        if (nums == null || nums.length <= 2) {
            return ret;
        }
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {
            if (i == 0 || nums[i] != nums[i-1]) {
                twoSum(nums, -nums[i], i + 1, nums.length - 1, ret);   
            }
        }
        return ret;
    }
    
    
    private void twoSum(int[] nums, int target, int front, int end, List<List<Integer>> ret) {
        while (front < end) {
            if (nums[front] + nums[end] == target) {
                List<Integer> item = new ArrayList<Integer>();
                item.add(-target);
                item.add(nums[front]);
                item.add(nums[end]);
                ret.add(item);
                front++;
                while (front < end && nums[front] == nums[front - 1]) {
                    front++;
                }
            } else if (nums[front] + nums[end] < target) {
                front++;   
            } else {
                end--;
            }   
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.