LeetCode(Array&String)3Sum

3Sum

Given an array nums of n integers, are there elements a, b, c in nums 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.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

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

思路：三数求和，重点在于复杂度，能想到的枚举法，至少3层for循环嵌套，还得消除重复元素。

第一版算法无错但是超时的代码如下：

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
         int len=nums.length;
        List<List<Integer>> res=new ArrayList<List<Integer>>();
        for(int i=0;i<len;i++){
            for(int j=i+1;j<len;j++){
                for(int k=j+1;k<len;k++){
                    if(nums[i]+nums[j]+nums[k]==0){
                        List<Integer> list=new ArrayList<Integer>();
                        list.add(nums[i]);
                        list.add(nums[j]);
                        list.add(nums[k]);
                        if(res.size()==0) {
                        	res.add(list);
                        }else {
                             //避免重复元素
                        	 int count=0;
                        	 for(int h=0;h<res.size();h++){
                                 List<Integer> temp=res.get(h);
                                 temp.sort(null);
                                 list.sort(null);
                                 if(list.equals(temp)){
                                      count++;
                                 }
                            }
                        	 if(count==0) {
                        		 res.add(list);
                        	 }
                        	
                        }
                    }
                }
            }
        }
        return res;
    }
}

想到排序后的数组更有规律，方便操作，改进后的代码如下：

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        int len=nums.length;
        List<List<Integer>> res=new ArrayList<List<Integer>>();
        if(len<3){
            return res;
        }
        //排序后数组更有规律，方便操作
        Arrays.sort(nums);
        int i=0;
        while(i<len-2){
            int start=i+1;
            int end=len-1;
            while(start<end){
                int sum=nums[i]+nums[start]+nums[end];
                
                if(sum==0){
                    res.add(Arrays.asList(nums[i],nums[start],nums[end]));
                    do{
                        end--;
                    }while(start<end && nums[end]==nums[end+1]);
                    do{
                        start++;
                    }while(start<end && nums[start]==nums[start-1]);
                }else if(sum>0){
                    do{
                        end--;
                    }while(start<end && nums[end]==nums[end+1]);
                }else{
                    do{
                        start++;
                    }while(start<end && nums[start]==nums[start-1]);
                }
            }
            do{
                i++;
            }while(i<len-2 && nums[i]==nums[i-1]);
        }
        return res;
    }
}