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

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

示例：

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

满足要求的三元组集合为：
[
　　[-1, 0, 1],
　　[-1, -1, 2]
]
第一种思路：
利用到二分搜索的思想，难点是在于去掉重复选取的问题，

1. 首先将数组排序Arrays.sort(nums)。
2. 循环遍历排序后的数组，选取第一个元素用 i 表示下标。
   1). 对第一个元素进行检查，如果 nums[i] 大于0，则结束循环。因为数组已经有序了，i 后面的元素也都全大于0。if(nums[i] > 0) break;
   2). 从 i + 1 开始循环选取第二个元素，用 j 表示第二个元素下标。
   　a. 然后利用二分搜索的思想在j + 1 到 nums.length之间寻找第三个元素。
   　b. 对第二个元素去重，在第二层循环中，每次选取第三个元素后，都要对第二个元素j检查是否有重复的元素，跳过重复的元素。 while(j < nums.length-1 && nums[j] == nums[j+1]) j++;
   3). 第二层循环结束后， 对第一个元素去重。while(i < nums.length-1 && nums[i] == nums[i+1]) i++;

class Solution {
   
    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> allSum = new ArrayList<>();
        // 排序
        Arrays.sort(nums);
        int num;
        int index;  // 第三个元素的下标。
        for (int i = 0; i < nums.length - 1; i ++){

            if(nums[i] > 0)  // 右边大于0，后面的无解
                break;
          
            for(int j = i+1; j < nums.length - 1; j ++){
               // 前两个元素的和
                num = nums[i] + nums[j];
                // 利用到二分搜索查找第三个元素。
                index = Arrays.binarySearch(nums, j+1, nums.length, -num);
                // 找到元素的情况
                if (index >= 0){
                    List<Integer> sum = new ArrayList<>(3);
                    sum.add(nums[i]);
                    sum.add(nums[j]);
                    sum.add(nums[index]);
                    allSum.add(sum);    
                }
                // 第二个元素去重
                while(j < nums.length-1 && nums[j] == nums[j+1])
                        j++;
            }
            // 第一个元素去重
            while(i < nums.length-1 && nums[i] == nums[i+1])
                i++;
        }
        return allSum;
    }

}

执行结果：通过显示详情
执行用时 :108 ms, 在所有 Java 提交中击败了14.92%的用户。
内存消耗 :45.3 M, 在所有 Java 提交中击败了96.53%的用户。

第一种方法消耗的时间太长了。然后查看了评论区发现了第二种思路。

第二种思路：
使用双指针在数组中动态选取元素。

1. 对数组进行排序，Arrays.sort(nums)。
2. 循环遍历数组，选取第一个元素用 i表示其下标。
   1). 对第一个元素进行检查，如果 nums[i] 大于0，则结束循环 。
   2). 用左指针 left 选取第二个元素 left = i + 1，右指针 right 选取第三个元素 right = nums.length - 1。
   3). 当 left < right 时，执行第二层循环遍历数组。
   　　a. 当 nums[i] + nums[left] + nums[right] == 0 时，说明找到了解，保存元素，同时需要检查左右指针指向的元素是否与下一个解相同，去掉重复的解，移动左右指针 left ++, right--，寻找下一个解。
   　　b.　当 nums[left] + nums[right] ＜ 0 - nums[0]，此时 nums[left] 的值偏小，移动左指针 left++。
   　　c. 当 nums[left] + nums[right] > 0 - nums[0], 此时 nums[right] 的值偏大，移动右指针right --;
   4). 结束第二层循环后，同样需要对第一个元素 i 进行去重操作。

class Solution {

    public static List<List<Integer>> threeSum(int[] nums){
          List<List<Integer>> allSum = new ArrayList<>();
          // 排序
          Arrays.sort(nums);
          
          for(int i = 0; i < nums.length - 2; i++){
            
            if(nums[i] > 0)  // nums[i] 等于0，后面的也就全部大于0;
                break;
            int left = i + 1, right = nums.length - 1;
            int sum = 0 - nums[i];
            while(left < right){
                if(nums[left] + nums[right] == sum){
                    allSum.add(Arrays.asList(nums[i], nums[left], nums[right]));

                    // 去重
                    while(left < right && nums[left] == nums [left+1]) left ++;
                    // 去重
                    while(left < right && nums[right] == nums[right-1]) right --;

                    left ++;
                    right --;
                }else if(nums[left] + nums[right] < sum){
                    left ++;
                }else{
                    right --;
                }
            }
            // 去重
            while( i < nums.length - 2 && nums[i] == nums[i+1])
                i ++; 
          }
        return allSum;
    }
}