三个整数之和

描述

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

题解

1.运用排序加三指针的方法。如果使用暴力法，三层循环遍历时间复杂度O(N^3)，显然是不符合要求的，考虑先将数组排序，三个数之和为0，必然是有负数才能满足。对数组排序一次，定义三个指针分别为最左边的指针min(对应数组中最小的数)，左右指针分别为leftIndex、rightIndex。其遍历的范围即为([min+1, nums.length-1])。
2.当leftIndex与rightIndex遍历的结果满足nums[min]+nums[leftIndex]+nums[rightIndex]=0，即为满足条件的三元组nums[min]、nums[leftIndex]、nums[rightIndex]。
3.当nums[min]>0，跳出循环，因为min对应的是最小数，则往后没有满足的条件。
4.当min>0 && nums[min] == nums[min-1]，则跳过nums[min]，因为如果不跳过则会出现重复的三元组。
5.循环的条件leftIndex<rightIndex，从([min+1, nums.length-1])向中间遍历，sum=nums[min]+nums[leftIndex]+nums[rightIndex]。

当sum>0：要移动rightIndex，这个很好理解，我们的rightIndex对应的数组中较大的数，sum>0，减小nums[rightIndex]的值，sum才会靠近0，rightIndex–。
当sum<0：同理，leftIndex对应较小的值，移动leftIndex，nums[leftIndex]值增大。sum靠近0，leftIndex++。
当sum=0：记录满足的三元组。

6.时间负责度O(N^2)，空间复杂度O(1)。排序的复杂度为O(NlogN)。

实现

public List<List<Integer>> threeNumSum(int[] numArray) {
    if (numArray == null || 0 == numArray.length) {
        return new ArrayList<>();
    }
    Arrays.sort(numArray);
    List<List<Integer>> result = new ArrayList<>();
    for (int min = 0; min < numArray.length - 2 ; min++) {
          if(numArray[min] > 0) break;
          if(min > 0 && numArray[min] == numArray[min-1]) continue;
          int leftIndex = min+1, rightIndex = numArray.length - 1;
          int sum = numArray[min] + numArray[leftIndex] + numArray[rightIndex];
          while(leftIndex<rightIndex) {
              if (sum < 0) {
                while(leftIndex < rightIndex && numArray[leftIndex] == numArray[++leftIndex]);
              } else if(sum > 0) {
                while(leftIndex < rightIndex && numArray[rightIndex] == numArray[--rightIndex]);
              } else {
                result.add(new ArrayList<>(Arrays.asList(numArray[min], numArray[leftIndex], numArray[rightIndex])));
                while(leftIndex < rightIndex && numArray[leftIndex] == numArray[++leftIndex]);
                while(leftIndex < rightIndex && numArray[rightIndex] == numArray[--rightIndex]);
              }
          }
    }
    return result;
}

Tips

1.注意++i与i++的区别。