Simple Java solution beats 78% using two pointers


  • 1
    D
    public class Solution {
        public List<List<Integer>> fourSum(int[] nums, int target) {
            Arrays.sort(nums);
            List<List<Integer>> res=new LinkedList<>();
            for(int i=0;i<nums.length-3;i++){
                int sum=target-nums[i];
                for(int j=i+1;j<nums.length-2;j++){
                    int left=j+1,right=nums.length-1;
                    int sumf=sum-nums[j];
                    while(left<right){
                        if(nums[left]+nums[right]==sumf){
                            res.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));
                            while(left<right&&nums[left]==nums[left+1]) left++;
                            while(left<right&&nums[right]==nums[right-1]) right--;
                            left++;right--;
                        }else if(nums[left]+nums[right]>sumf) right--;
                        else left++;
                    }
                    while(j<nums.length-3&&nums[j]==nums[j+1]) j++;
                }
                while(i<nums.length-4&&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.