Clean accepted java O(n^3) solution based on 3sum


  • 86
    C
    public class Solution {
    public List<List<Integer>> fourSum(int[] num, int target) {
        ArrayList<List<Integer>> ans = new ArrayList<>();
        if(num.length<4)return ans;
        Arrays.sort(num);
        for(int i=0; i<num.length-3; i++){
            if(num[i]+num[i+1]+num[i+2]+num[i+3]>target)break; //first candidate too large, search finished
            if(num[i]+num[num.length-1]+num[num.length-2]+num[num.length-3]<target)continue; //first candidate too small
            if(i>0&&num[i]==num[i-1])continue; //prevents duplicate result in ans list
            for(int j=i+1; j<num.length-2; j++){
                if(num[i]+num[j]+num[j+1]+num[j+2]>target)break; //second candidate too large
                if(num[i]+num[j]+num[num.length-1]+num[num.length-2]<target)continue; //second candidate too small
                if(j>i+1&&num[j]==num[j-1])continue; //prevents duplicate results in ans list
                int low=j+1, high=num.length-1;
                while(low<high){
                    int sum=num[i]+num[j]+num[low]+num[high];
                    if(sum==target){
                        ans.add(Arrays.asList(num[i], num[j], num[low], num[high]));
                        while(low<high&&num[low]==num[low+1])low++; //skipping over duplicate on low
                        while(low<high&&num[high]==num[high-1])high--; //skipping over duplicate on high
                        low++; 
                        high--;
                    }
                    //move window
                    else if(sum<target)low++; 
                    else high--;
                }
            }
        }
        return ans;
    }
    

    updated with optimizations and comments


  • 0
    Z

    nice answer! you can add a link to 3 sum , so people can see their similarity


  • 0
    This post is deleted!

  • 0

  • 0

    @casualhero

    sorry to know it got TLE now


  • 1
    C

    @Lara
    Add the following sentence could avoid TLE, and win over more than 80%.
    if(4 * nums[0] > target || 4 * nums[len - 1] < target) return result;


  • 0

    @CrazyT good idea


  • 0
    R

    I use the method also base on 3sum
    ""
    public List<List<Integer>> fourSum(int[] nums, int target) {
    List<List<Integer>> list=new LinkedList<List<Integer>>();
    Arrays.sort(nums);
    for(int i=0;i<nums.length-3;){
    threeSum(nums, i, target-nums[i], list);
    do{i++;}while(i<nums.length-3&&nums[i]==nums[i-1]);
    }
    return list;
    }

    public void threeSum(int[] nums,int index, int target,List<List<Integer>> list ) 
    {
    	int height,low,subRes;
    	for(int i=index+1;i<nums.length-2;)
    	{
    		low=i+1;height=nums.length-1;
    		while(low<height)
    		{
    			subRes=nums[i]+nums[low]+nums[height];
    			if(subRes==target) 
    			{
    				list.add(new ArrayList<Integer>(Arrays.asList(new Integer(nums[index]),new Integer(nums[i]),new Integer(nums[low]),new Integer(nums[height])) ));
    				if(nums[low]==-2&&nums[height]==0)
    					System.out.println("*****debug*****");
    				do{low++;height--;}while(low<height&&nums[low]==nums[low-1]&&nums[height]==nums[height+1]);
    				}
    			else{
    				if(subRes>target) {height--;}
    				else {low++;}
    			}
    		}
    		do{i++;}while(i<nums.length-2&&nums[i]==nums[i-1]);
    	}
    }

  • 0
    S

    @casualhero nice answer.

    I wonder if anyone could explain here, why, while the first two elements of the quadruple can 'skip' the replicate (the 2 'continue'), the last two elements (marked by 'low' and 'high') only do the 'skipping' when we found a valid quadruple?

    Thanks!


  • 0
    J

    @CrazyT Hi, why add this line of code? Thank you so much.


  • 0
    N

    @Lara Where exactly should that line be added?


  • 3
    6

    Inspired by the top1 "7ms solution", add two more condition sentences in each “for()” loops will save a lot of runtime which only 26ms,can beats 98.16%;

    public class Solution {
        public List<List<Integer>> fourSum(int[] nums, int target) {
            List<List<Integer>> res=new LinkedList<>();
            if(nums.length<4) return res;
            Arrays.sort(nums);
            for(int i=0;i<nums.length-3;i++){
                if(i>0&&nums[i]==nums[i-1]) continue;
                
                if(nums[i]*4>target) break;// Too Big!!
                if(nums[i]+3*nums[nums.length-1]<target) continue;//Too Small
                
                for(int j=i+1;j<nums.length-2;j++){
                    if(j>i+1&&nums[j]==nums[j-1]) continue;
                    
                    if(nums[j]*3>target-nums[i]) break;//Too Big
                    if(nums[j]+2*nums[nums.length-1]<target-nums[i]) continue;// Too Small
                    
                    int begin=j+1;
                    int end=nums.length-1;
                    while(begin<end){
                        int sum=nums[i]+nums[j]+nums[begin]+nums[end];
                        if(sum==target){
                            res.add(Arrays.asList(nums[i],nums[j],nums[begin],nums[end]));
                            while(begin<end && nums[begin]==nums[begin+1]){begin++;}
                            while(begin<end && nums[end]==nums[end-1]){end--;}
                            begin++;
                            end--;
                        }else if (sum<target){
                            begin++;
                        }else{
                            end--;
                        }
                    }
                }
            }
        return res;
        }
    }
    

  • 0
    C

    @61m nice optimizations. I have updated the post with them


  • 0
    C

    @stochastika said in Clean accepted java O(n^3) solution based on 3sum:

    d by 'low' and 'high

    the fist two prevents duplicate results. in the windows I skip over duplicates in order to find other possible results


  • 0
    M

    @61m said in Clean accepted java O(n^3) solution based on 3sum:

    if(nums[i]4>target) break;// Too Big!!
    if(nums[i]+3
    nums[nums.length-1]<target) continue;//Too Small

    Please let me know what the purpose of multilying by 4 or 3


  • 0

    Actually the first two statements inside second for loop are unnecessary. Because j starts from i + 1, so in the first for loop you already check the candidate.


Log in to reply
 

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