My java solution[Iterate first element and reduce to 3sum, easy to understand]


  • 0
    Y
    public class Solution {
        public List<List<Integer>> fourSum(int[] nums, int target) {
            Arrays.sort(nums);
            ArrayList<List<Integer>> res=new ArrayList<List<Integer>>();
            for (int i=0;i<nums.length-3;i++){
                int sum3=target-nums[i];
                for(int j=i+1;j<nums.length-2;j++){
                    int sum2=sum3-nums[j];
                    int k=j+1;
                    int l=nums.length-1;
                    while(k<l){
                        if(nums[k]+nums[l]<sum2){
                            k++;
                        }else if(nums[k]+nums[l]>sum2){
                            l--;
                        }
                        else{
                            ArrayList<Integer> quad=new ArrayList<Integer>();
                            quad.add(nums[i]);
                            quad.add(nums[j]);
                            quad.add(nums[k]);
                            quad.add(nums[l]);
                            res.add(quad);
                            while(k<nums.length-1 && nums[k]==nums[k+1])k++;
                            while(l>j&&nums[l]==nums[l-1])l--;
                            k++;
                            l--;
                        }
                    }
                    while(j<nums.length-2 && nums[j]==nums[j+1])j++;
                }
                while(i<nums.length-3 && nums[i]==nums[i+1]) i++;
            }
            return res;
        }
    }
    

Log in to reply
 

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