15. 三数之和

第一种解法

class Solution {
        public List<List<Integer>> threeSum(int[] nums) {
            List<List<Integer>> ls = new ArrayList<List<Integer>>();
            if(nums == null || nums.length < 3)
                return ls;
            Arrays.sort(nums);
            if(nums[0] > 0 || nums[nums.length - 1] < 0)
                return ls;
            for(int i = 0 ; i < nums.length-2 ; i++){
                if(i != 0 && nums[i] == nums[i - 1])
                    continue;
                int j = i +1;
                int z = nums.length - 1;
                while(j<z&&nums[i]<1){
                    int sum = nums[i]+nums[j]+nums[z];
                    if(sum==0){
                        ArrayList al = new ArrayList<Integer>();
                        al.add(nums[i]);
                        al.add(nums[j]);
                        al.add(nums[z]);
                        ls.add(al);
                        j++;
                        z--;
                        while(j<z&&nums[j]==nums[j-1])j++;//防止重复添加
                        while(j<z&&nums[z]==nums[z+1])z--;
                    }
                    else if(sum<=0)//左边太小
                        j++;
                    else z--;
                }
            }
            return ls;
        }
    }

思路：从小排到大，然后利用双指针进行 大的向左 小的向右
总结：虽然思路很简单，但是里面有一些细节，如：重复问题(利用nums[i] nums[i-1] 【i已经先加1】，然后nums[j-1] nums[j] 以及nums[z] nums[z+1]【z已经减一了】)

• 进行部分优化

  class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ls = new ArrayList<List<Integer>>();
        if(nums == null || nums.length < 3)
            return ls;
        Arrays.sort(nums);
        if(nums[0] > 0 || nums[nums.length - 1] < 0)
            return ls;
        for(int i = 0 ; i < nums.length-2 ; i++){
            if(i != 0 && nums[i] == nums[i - 1])
                continue;
            int j = i +1;
            int z = nums.length - 1;
            while(j<z&&nums[i]<1){
                int sum = nums[i]+nums[j]+nums[z];
                if(sum==0){
                    ArrayList al = new ArrayList<Integer>();
                    al.add(nums[i]);
                    al.add(nums[j]);
                    al.add(nums[z]);
                    ls.add(al);
                    j++;
                    z--;
                    while(j<z&&nums[j]==nums[j-1])j++;//防止重复添加
                    while(j<z&&nums[z]==nums[z+1])z--;
                }
                else if(sum<=0)//左边太小
                    j++;
                else z--;
            }
            while(i<nums.length-1&&nums[i]==nums[i+1])i++;//排除掉重复
        }
        return ls;
    }
  }