ThreeNums(LeetCode)

文章目录

1. 1. Question:3Sum
2. 2. SourceCode:
   1. 2.1. s1
   2. 2.2. s2

Question:3Sum

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? 

Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

SourceCode:

s1

//笔者提交版本；耗时：67ms；
public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        
        int len = nums.length;
        if(len < 3){return result;}
        
        Set<ArrayList<Integer>> resultSet = new HashSet<>();
        
        Arrays.sort(nums);
        
        for(int i = 0;i<len-2;i++){
            for(int j = i+1;j<len-1;j++){
                int target = 0 - nums[i] - nums[j];
                
                if(target < 0){
                    break;
                }
                
                int k = Arrays.binarySearch(nums,j+1,len,target);
                if(0 <= k){
                    ArrayList<Integer> tmpArray = new  ArrayList<Integer>();
                    tmpArray.add(nums[i]);
                    tmpArray.add(nums[j]);
                    tmpArray.add(nums[k]);
                    resultSet.add(tmpArray);
                }
            }
            
        }
        
        for(List<Integer> elem :resultSet){
            result.add(elem);
        }
        
        return result;
    }
}

s2

//该版本参考了Discuss,重新整理优化；耗时：8ms；
public class Solution {
        public List<List<Integer>> threeSum(int[] nums) {
        int len = nums.length;
		List<List<Integer>>  result = new ArrayList<List<Integer>>();
        
		if(len < 3){
			return result;
		}
        
		//经过排序后，数据分为 负数区，0区，和正数区；
		Arrays.sort(nums);
		
		for(int i = 0, jLoc = len -1 , iLoc = len - 2; i < iLoc ; i++){
			
			int target = 0 - nums[i];
			int jStart = i+1;
			int jEnd = jLoc;
			
			//进入正数区
			if(target < 0 ){
				break;
			}
			
			while(jStart < jEnd){
				int sum = 0;
				if(target == (sum = nums[jStart] + nums [jEnd])){
				
					addElemnts(result,nums[i],nums[jStart],nums[jEnd]);
					
					//去掉重复元素
					while(jStart < jEnd && nums[jEnd-1] == nums[jEnd]){
						jEnd--;
					}
					while(jStart < jEnd && nums[jStart+1] == nums[jStart]){
						jStart++;
					}
					
					jEnd--;
					jStart++;
				}else if(target < sum ){
					jEnd--; 
				}else{
					jStart++;
				}
			}
			
			//去掉重复元素
			while((i < iLoc )&& nums[i+1] == nums[i]){
				i++;
			}
			
		}
		
        return result;
    }
	
	public void addElemnts(List<List<Integer>>  result,int a,int b,int c){
		List<Integer> tmpArr = new ArrayList<Integer>();
		tmpArr.add(a);
		tmpArr.add(b);
		tmpArr.add(c);
		result.add(tmpArr);
	}
}