LeetCode每日一题：三数之和

• 解题思路：还是熟悉的双指针法
  • 首先把数组nums从小到大进行排序，然后取一个固定的数nums[i]，左指针left = i+1，右指针right = nums.length - 1;
  • 三数之和sum = nums[i] + nums[left] + nums[right]
    如果sum = 0，则返回i，left，right；如果sum > 0，则right--；如果sum < 0，则left++。
  • 去重：当 sum == 0 时，nums[left] == nums[left+1] 则会导致结果重复，应该跳过，则left++；nums[right] == nums[right-1]则会导致结果重复，应该跳过，则right--

代码实现：

   public  List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        ArrayList<List<Integer>> list = new ArrayList<>();
          for(int i = 0;i <= nums.length-3;i++){
              int left = i+1;
              int right = nums.length-1;  
              if(nums[i]>0){break;} //nums[i] > 0时就不需要再遍历了
              if(i>=1 && nums[i] == nums[i-1]) {continue;}
              while(left < right){
             int s = nums[i] + nums[left] + nums[right];
              if(s == 0 ){
                  list.add(Arrays.asList(nums[i],nums[left],nums[right]));
                  //接下来就是去重操作
                  while(nums[left] == nums[left + 1] && left < right-1){
                     left++;
                 }
                  while(nums[right] == nums[right - 1] && left+1 < right){
                     right--;
                 } 
                left++;
                 right--;
              }else if(s < 0){left++;}
              else if(s > 0){right--;}
            }
          }
          return list;
       }