Accepted Java solution


  • 2
    D

    Another for loop is added to the 3Sum solution and we have this.

    public class Solution {
        public List<List<Integer>> fourSum(int[] num, int target) {
            List<List<Integer>> result = new ArrayList<List<Integer>>();
            if (num.length < 4) {
                return result;
            }
            Arrays.sort(num);
            
            for (int i = 0; i < num.length - 3; i++) {
                if (i > 0 && num[i] == num[i - 1]) {
                    continue;
                }
                for (int j = num.length - 1; j > i + 2; j--) {
                    if (j < num.length - 1 && num[j] == num[j + 1]) {
                        continue;
                    }
                    int start = i + 1;
                    int end = j - 1;
                    int n = target - num[i] - num[j];
                    while (start < end) {
                        if (num[start] + num[end] == n) {
                            List<Integer> four = new ArrayList<Integer>();
                            four.add(num[i]);
                            four.add(num[start]);
                            four.add(num[end]);
                            four.add(num[j]);
                            result.add(four);
                            do { start++; } while (start < end && num[start] == num[start - 1]);
                            do { end--; } while (start < end && num[end] == num[end + 1]);
                        }
                        else if (num[start] + num[end] < n) {
                            do { start++; } while (start < end && num[start] == num[start - 1]);
                        }
                        else {
                            do { end--; } while (start < end && num[end] == num[end + 1]);
                        }
                        
                    }
                }
            }
            
            return result;
        }
    }

  • 2
    S

    Same Solution for reference. Can be generalized to k-sum.

    public class Solution {
        public List<List<Integer>> fourSum(int[] num, int target) {
            List<List<Integer>> rslt = new ArrayList<List<Integer>>();
            Arrays.sort(num);
            for(int i = 0;i < num.length-3;i++){
                if(i==0 || i> 0 && num[i]!=num[i-1]){
                for(int j = i+1;j < num.length-2;j++){
                    if(j==i+1 || j > i+1 && num[j]!= num[j-1]){
                    int rest = target - num[i] - num[j];
                    int low = j+1, high = num.length-1;
                    while(low < high){
                        int sum = num[low] + num[high];
                        if(sum == rest){
                            List<Integer> list = new ArrayList<Integer>();
                            list.add(num[i]);
                            list.add(num[j]);
                            list.add(num[low]);
                            list.add(num[high]);
                            rslt.add(list);
                            while(high > low && num[high] == num[--high]);
                            while(high > low && num[low] == num[++low]);
                        }
                        else if(sum > rest)
                            high--;
                        else
                            low++;
                        
                    }
                    }
                }
                }
            }
            return rslt;   
        }
    }
    

  • 0
    H

    My algorithm is similar to the original author, but I use HashSet to check for duplicates. Thus, it is very to understand.

    public class Solution {
        public List<List<Integer>> fourSum(int[] nums, int target) {
            Arrays.sort(nums);
            List<List<Integer>> result = new ArrayList<List<Integer>>();
            // set for checking duplicate quadruplet
            Set<List<Integer>> preResult = new HashSet<List<Integer>>();
            if (nums.length < 4) return result;
            // the two pointers
            int low = 0, high = 0;
            
            for (int i = 0; i < nums.length - 3; i++) {
                for (int j = i+1; j < nums.length - 2; j++) {
                    low = j+1;
                    high = nums.length - 1;
                    // while the two pointers do not meet
                    while (low < high) {
                        if (nums[i]+nums[j]+nums[low]+nums[high] == target) {
                            List<Integer> list = new ArrayList<Integer>();
                            list.add(nums[i]);
                            list.add(nums[j]);
                            list.add(nums[low]);
                            list.add(nums[high]);
                            // add the solution to the set first
                            preResult.add(list);
                            // check for the next combination
                            low++;
                            high--;
                        }
                        else if (nums[i]+nums[j]+nums[low]+nums[high] > target) {
                            high--;
                        }
                        else {
                            low++;
                        }
                    }
                }
            }
            // copy the elements in the set into the list for final answer
            for (List<Integer> ls:preResult) {
                result.add(ls);
            }
            return result;
        }
    }

Log in to reply
 

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