3sum solution in java O(n^2)


  • 0
    S
    public class Solution15 {
    	    List<List<Integer>> list = new ArrayList<List<Integer>>();
    	    public List<List<Integer>> threeSum(int[] nums) {
    	    	if(nums==null||nums.length<3){
    	    		return list;
    	    	}
    	    	int length = nums.length;
    	    	Arrays.sort(nums);
    	    	for(int i = 0; i<length-2; i++){
    	    		if(nums[i]+nums[i+1]>0){
    					break;
    				}
    	    		if (i > 0 && nums[i] == nums[i - 1])
    	                continue;
    	    		getThreeSum(nums,i+1,length-1,nums[i]);
    	    	}
    	    	return list;
    	    }
    	    public void getThreeSum(int[] nums, int front, int behind, int target){
    	    	while(front<behind){
    	            if(target+nums[front]>0){
    	                break;
    	            }
    				if((nums[front]+nums[behind]+target)==0){
    					List<Integer> l = new ArrayList<Integer>();
    					l.add(target);
    					l.add(nums[front]);
    					l.add(nums[behind]);
    					list.add(l);
    					while(front<behind&&nums[behind]==nums[behind-1]){
    						behind--;
    					}
    	                behind--;
    					while(front<behind&&nums[front]==nums[front+1]){
    						front++;
    					}
    	                front++;
    				}else if((nums[front]+nums[behind]+target)>0){
    					behind--;
    				}else{
    					front++;
    				}
    			}
    	    }
    	}
    
    

Log in to reply
 

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