Pretty modularized solution in Java


  • 0
    L

    The idea is to break this into subproblems so it doesn't look like a giant block of code. Pretty much for every value in the array do a three sum for the rest of the array and make sure to filter out duplicates so you don't have to use sets instead. And tada, you are done!

    public List<List<Integer>> fourSum(int[] nums, int target) {
            List<List<Integer>> result = new ArrayList<>();
            Arrays.sort(nums);
            for (int i = 0; i < nums.length; i++){
                int check = target - nums[i];
                if (i > 0 && nums[i-1] == nums[i]) continue;
                List<List<Integer>> getThreeSums = threeSum(nums, i+1, nums.length -1, check);
                for (List<Integer> subList : getThreeSums){
                    subList.add(nums[i]);
                    result.add(subList);
                }
            }
            return result;
        }
       
    public List<List<Integer>> threeSum(int[] nums, int begin, int finish, int target){
            List<List<Integer>> result = new ArrayList<>();
            for (int i = begin; i <= finish; i++){
                if (i > begin && nums[i-1] == nums[i]) continue;
                int start = i + 1; int end = finish;
                int check = target - nums[i];
                while (start < end){
                    int twoSum = nums[start] + nums[end];
                    if (twoSum > check) end--;
                    else if (twoSum < check) start++;
                    else {
                        List<Integer> subResult = new ArrayList<>();
                        subResult.add(nums[i]); subResult.add(nums[start++]); subResult.add(nums[end--]);
                        result.add(subResult);
                        while(start < end && nums[start] == nums[start - 1]) start++;
                        while(start < end && nums[end] == nums[end + 1]) end--;
                    }
                }
            }
            return result;
        }
    

Log in to reply
 

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