三数之和

题目

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

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

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

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

思路

基本的思路：确定前两个数，用二分法找第三个数
需要注意的点：重复数字的处理
注：我这个写法效率不高，在leetcode-cn上排名靠后；高效的算法稍后更新：

代码

class Solution {
  public List<List<Integer>> threeSum(int[] nums) {
       Arrays.sort(nums);
       int len = nums.length;
       //remove repate number
       int j = 0;

       List<List<Integer>> answer = new LinkedList<List<Integer>>();

      //i指向第一个数，j指向第二个数
       for(int i = 0; i < len - 1; i++) {
           //避免第一个数重复
           if(i > 0 && nums[i] == nums[i-1])
               continue;
           for(j = i + 1; j <  len; j++) {
               //避免第一个数确定的情况下，第二个数重复
               if(j > i + 1 && nums[j] == nums[j-1])
                   continue;
               int thirdIndex = myBinarySearch(nums,0-nums[i]-nums[j]);
               if(thirdIndex > 0 && thirdIndex > j) {
                   List<Integer> ans = new LinkedList<Integer>();
                   ans.add(nums[i]);
                   ans.add(nums[j]);
                   ans.add(nums[thirdIndex]);
                   answer.add(ans);
               }
           }
       }

       return answer;
   }

  //二分法查找元素,如果有多个相同的则取最后一个
   private static int myBinarySearch(int[] nums,int target) {
       if(nums == null || nums.length <= 0) 
           return -1;
       int center;
       int i = 0,j = nums.length - 1;
       while(i <= j) {
           center = (i + j) / 2;
           if(nums[center] == target) {
                     //取最后一个
               while(center <= j && nums[center] == target)
                   center++;
               center--;
               return center;
           }
           else if(nums[center] > target)
               j = center - 1;
           else
               i = center + 1;
       }
       return -1;
   } 
}