An easy solution with explaination [JAVA]


  • 0
    L

    The solution can be described as:
    1) sort nums[] increasingly;
    2) try all the triples.
    Note that :
    1) in the outer loop, we just need all the numbers <= 0;
    2) since each number can appear repeated, we need to skip numbers that have been checked in the outer loop and median loop.

    '''
    public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
    int n = nums.length;
    List<List<Integer>> res = new ArrayList<List<Integer>>();

    	for(int i = 1; i < n; 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;
    	}
    	
    	int min = Integer.MIN_VALUE;
    	for(int i = 0; i < (n - 2) && nums[i] <= 0 ; i++){
    		
    		while( (nums[i] == min) && (i < (n-2))){ i++;}//跳过重复的数字
    		if( i == (n-2)){ break;}
    		int min2 = Integer.MIN_VALUE;
    		for( int j = i + 1; j < (n - 1); j++ ){
    			
    			while( nums[j] == min2 && j < (n - 1)){ j++;} // 跳过重复的数字
    			if( j == (n - 1)){ break;}
    			
    			for( int k = j + 1; k < n; k ++){
    				int sum =  nums[i] + nums[j] + nums[k];
    				if(sum == 0){
    					List<Integer> tem = new ArrayList<Integer>();
    					tem.add(nums[i]);
    					tem.add(nums[j]);
    					tem.add(nums[k]);
    					res.add(tem);
    					break;
    				}else if( sum > 0){
    					break;
    				}
    			}//for
    			min2 = nums[j];
    		}//for
    		min = nums[i];
    	}//for
    	
    	return res;
    }
    

    }
    '''


  • 0
    L

    @lyinr The algorithm is not effective enough for 3sum. However, by applying this algorithm to 4sum, you can beat 79% of java submissions.


Log in to reply
 

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