0015 三数之和.md

0015 三数之和

Question:

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 *a，b，c ，*使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

**注意：**答案中不可以包含重复的三元组。

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

Solution:

class Solution {
    public int BinarySearch(int[] nums,int num,int left,int right){
        int mid;
        while(left<=right){
            mid=(left+right)/2;
            if(nums[mid]<num)
                left=mid+1;
            else if(nums[mid]>num)
                right=mid-1;
            else
                return mid;
        }
        return -1;
    }
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> tuples=new LinkedList<>();
        Arrays.sort(nums);
        int zeroIndex=-1;
        boolean neg=false;
        boolean pos=false;
        for(int i=0;i<nums.length;i++){
            if(nums[i]<0)
                neg=true;
            else if(nums[i]>0)
                pos=true;
            else
                zeroIndex=i;
        }
        if(zeroIndex>=2){
            if(nums[zeroIndex-1]==0&&nums[zeroIndex-2]==0)
                tuples.add(Arrays.asList(0,0,0));
        }
        if(!(neg&&pos))
            return tuples;
        int index=BinarySearch(nums,0,0,nums.length-1);
        int negIndex=0;
        while(nums[negIndex+1]<0)
            negIndex++;
        int posIndex=nums.length-1;
        while(nums[posIndex-1]>0)
            posIndex--;
        if(index!=-1){
            for(int i=0;i<negIndex+1;){
                int a=nums[i];
                int cIndex=BinarySearch(nums,-a,posIndex,nums.length-1);
                if(cIndex!=-1){
                    tuples.add(Arrays.asList(a,0,-a));
                }
                while(i<=negIndex&&nums[i]==a)
                    i++;
            }
        }
        for(int i=0;i<negIndex;){
            int a=nums[i];
            for(int j=i+1;j<negIndex+1;){
                int b=nums[j];
                int c=-(a+b);
                int cIndex=BinarySearch(nums,c,posIndex,nums.length-1);
                if(cIndex!=-1){
                    tuples.add(Arrays.asList(a,b,c));
                }
                while(j<=negIndex&&nums[j]==b)
                    j++;
            }
            while(i<=negIndex-1&&nums[i]==a)
                i++;
        }
        for(int i=posIndex;i<nums.length-1;){
            int a=nums[i];
            for(int j=i+1;j<nums.length;){
                int b=nums[j];
                int c=-(a+b);
                int cIndex=BinarySearch(nums,c,0,negIndex);
                if(cIndex!=-1){
                    tuples.add(Arrays.asList(a,b,c));
                }
                while(j<=nums.length-1&&nums[j]==b)
                    j++;
            }
            while(i<=nums.length-2&&nums[i]==a)
                i++;
        }
        return tuples;
    }
}