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:

Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)

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)

思路：此题解法上不算难，可是通过率并不高。仅仅有16.9%。显然在其它地方存在限制。果然第一次提交測试的时候。果断TLE(超时)。代码效率上须要更快的速度。

第一次代码本地測试一组8ms左右。不能过。后面上网參看资料，写出改进的方法，同样的数据，本地測试2ms左右，效率约提高了4倍。

第一种方法代码：

public class Solution {

    public List<List<Integer>> threeSum(int[] nums) {

        if(nums.length < 2){

            return null;

        }

        //System.out.println(nums);

        Arrays.sort(nums);

        List<List<Integer>> list = new ArrayList<List<Integer>>();

        for(int i = 0; i < nums.length - 2; i++){

            if(nums[i] > 0)

        		 break;

        	if(i > 1 && nums[i] == nums[i-1]){

        		continue;

        	}

            for(int j = nums.length - 1; j > i + 1; j--){

                if(nums[j] < 0)

           		 	break;

            	if(j < nums.length -1 && nums[j] == nums[j+1]){

            		continue;

            	}

            	 //System.out.println(nums[i]);

                int c = -(nums[i] + nums[j]);

                int k = search(c,nums,i+1,j-1);

                if(k > 0){

                    List<Integer> al = new ArrayList<Integer>();

                    al.add(nums[i]);

                    al.add(nums[k]);

                    al.add(nums[j]);

                    list.add(al);

                }

            }

        }

        return list;

    }

    //二分查找数值c的位置,找到返回位置。找不到返回-1

    public static int search(int c,int[] nums,int start,int end){

        if(c < nums[start] || c > nums[end])

            return -1;

        int k = 0;

        while(start <= end){

            k = (start + end)/2;

            System.out.println(k);

            if(c > nums[k]){

                start = k + 1;

            }else if(c < nums[k]){

                end = k - 1;

            }

            else{

                return k;

            }

        }

        return -1;

    }

}

另外一种方法代码：

public class Solution {

	public List<List<Integer>> threeSum(int[] nums) {

	    List<List<Integer>> list = new ArrayList<List<Integer>>();

        if(nums.length < 2){

            return list;

        }

        Arrays.sort(nums);//数组排序

        int j,k,m;

        int len = nums.length;

        for(int i = 0; i < len - 2; i++){

        	//假设最小值依旧大于0或者最大值小于0，肯定没有符合要求的值。直接返回

        	 if(nums[i] > 0 || nums[len-1] < 0)

        		 break;

        	//假设如今的数字和之前的数字反复，直接跳出，继续下一下

        	if(i > 0 && nums[i] == nums[i-1]){

        		continue;

        	}

        	//初始值

        	j = i + 1;

        	k = len - 1;

        	while(j < k){

            	m = nums[i] + nums[j] + nums[k];//三者之和

            	if(m == 0){//=0。满足条件

            		List<Integer> al = new ArrayList<Integer>();

                    al.add(nums[i]);

                    al.add(nums[j]);

                    al.add(nums[k]);

                    list.add(al);

                    j++;

                    k--;

                    //假设相邻数字相等。则直接跳过，此处重要

                    while(j < k && nums[j] == nums[j-1]){

                		j++;

                	}

                    while(j < k && nums[k] == nums[k+1]){

                    	k--;

                    }

            	}else{

            		if(m > 0)//这里也是非常重要的点，分情况位置标记变动

            			k--;

            		else

            			j++;

            	}

        	}

        }

        return list;

    }

}