My easy java solution with explaination [ beating 79.87% of javasubmission]


  • 0
    L
    The basic idea is to **skip some numbers that are too small or too big for the target** 
    Assume len = nums.length();
    we say nums[i] is "**too small**" if and only if it satisfies nums[i] + nums[len-3] + nums[len-2] + nums[len-1] < target; and by skip the small numbers we get an index "start";
    Similarly, we say nums[j] is "too big" if and only if num[j] + nums[start] + nums[start+1] + nums[start+2] > target. Then we get another index "end".
    Then we can search nums[start: end] by brute force.
    
    PS: the method can be applied to solve "3sum". my submission for "3sum" is accepted but only beats 17% of java submissions.
    

    '''
    import java.util.ArrayList;
    import java.util.LinkedList;
    import java.util.List;

    public class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
    List<List<Integer>> ans = new LinkedList<List<Integer>>();
    int len = nums.length;

    	if( len < 4){
    		return ans;
    	}
    	
    	sort(nums,len);
    	    	
    	//To skip some small numbers
    	int start = 0;
    	for(int i = 0; i < len-3; i++){
    		if( nums[i] + nums[len-1] + nums[len-2] + nums[len-3] < target){
    			start = i;
    		}
    	}
    	
    	//To skip some big numbers
    	int end = len - 1;
    	for(int j = len - 1; j > 2; j--){
    		if( nums[j] + nums[start] + nums[start+1] + nums[start+2] > target){
    			end = j;
    		}else{
    			break;
    		}
    	}
    	
    	int min1 = Integer.MIN_VALUE;
    	
    	for( int i = start; i <= end-3; i++){//for-1
    		
    		/**/for( ; i <= end-3 && nums[i] == min1 ;){i++;} //To skip
    		
    		int min2 = Integer.MIN_VALUE;
    		for( int j = i + 1; j <= end-2; j++){//for-2
    			
    			/**/for( ; j <= end-2 && nums[j] == min2;){j++;} //To skip
    			
    			int min3 = Integer.MIN_VALUE;
    			for(int k = j + 1; k <= end-1; k++){//for-3
    				
    				/**/for(; k <= end-1 && nums[k]== min3 ;){k++;}//To skip
    				
    				for( int p = k + 1; p <=end; p++){//for-4
    					int sum = nums[i] + nums[j] + nums[k] + nums[p];
    					if( sum == target){    						
    						List<Integer> tem = new ArrayList<Integer>();
    						tem.add(nums[i]);
    						tem.add(nums[j]);
    						tem.add(nums[k]);
    						tem.add(nums[p]);
    						ans.add(tem);
    						break;
    					}else if( sum > target){
    						break;
    					}//if
    				}//for-4
    				min3 = nums[k];
    			}//for-3
    			min2 = nums[j];
    		}//for-2
    		min1 = nums[i];
    	}//for-1
    	return ans;
    }
    
    public void sort(int []nums, int len){
    	for(int i = 0; i < len; i++){
    		int insertpos = i;
    		for(int j = i - 1; j >=0; j--){
    			if(nums[i] < nums[j]){
    				insertpos = j;
    			}else{
    				break;
    			}
    		}
    		
    		int tem = nums[i];
    		for( int j = i; j > insertpos; j--){
    			nums[j] = nums[j-1];
    		}
    		nums[insertpos] = tem;
    	}
    }
    

    }
    '''


Log in to reply
 

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