Simple 82ms two pointers Java solution


  • 0

    Explanation

    The core algorithm is similar as 3sum, using two pointers to approach from start and end. Just added two limit pointers[i, j], before two pointers[start, end].

    public List<List<Integer>> fourSum(int[] num, int target)
    {
        ArrayList<List<Integer>> result = new ArrayList<List<Integer>>();       
        Arrays.sort(num);
        for (int j = 0; j < num.length; j++) {
    	    for (int i= j + 1; i < num.length; i++) {
    	        int start = i + 1, end = num.length-1;
    	        while (start < end) {//Two pointers
    	            int sum = num[j] + num[i] + num[start] + num[end];   
    
    	            if (sum == target) {     
    	                ArrayList<Integer> list = new ArrayList<Integer>();
    	                list.add(num[j]);		               
    	                list.add(num[i]);
    	                list.add(num[start]);
    	                list.add(num[end]);    
    	                result.add(list);
    
    	                start++;
    	                end--;
    	                while((start < end) && num[start] == num[start-1]) start++;     //remove duplicates
    	                while((start < end) && num[end] == num[end+1]) end--;
    	            }
    	            else if (sum < target) {
    	                start++;       
    	                while((start < end) && num[start] == num[start-1]) start++;     //remove duplicates
    	            } else {            
    	                end--;
    	                while((start < end) && num[end] == num[end+1]) end--;           //remove duplicates             
    	            }      
    	        }
    
    	        while (i+1 < num.length && num[i+1] == num[i])                          //remove duplicates
    	            i++;            
    	    }
    	    
            while (j+1 < num.length && num[j+1] == num[j])                          //remove duplicates
                j++;    
        }
    
        return result;
    }

  • 0

    I'm not sure how this got accepted. For 3Sum problem, O(n3) for naive approach was not acceptable and I dont think this performs better than O(n3).


  • 0

    Hi, Arun, thanks for the comment. Two pointers solution for 3Sum uses O(n^2) time, instead of O(n^3), because two pointers method will ignore duplicated cases. So 4Sum with two pointers solution uses O(n^3) time. Hope it will help;)


Log in to reply
 

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