给出一个有n个整数的数组S，在S中找到三个整数a, b, c，找到所有使得a + b + c = 0的三元组。

注意事项

在三元组(a, b, c)，要求a <= b <= c。

结果不能包含重复的三元组。

样例

如S = {-1 0 1 2 -1 -4}, 你需要返回的三元组集合的是：

(-1, 0, 1)

(-1, -1, 2)

标签

数组 排序 两根指针 脸书

思路

首先升序排序数组

然后定义下标变量 k , i , j 。如果简单的遍历，那么跟是否有序没有关系，其时间复杂度将达到O(n^3)。

但是，如果当前选择了a、b、c三个数，如果其和小于目标target，那么需要将其中一个数用更大的数替换；反之亦然。但究竟替换三个数中的哪个数？可以先固定一个数（k），当前值小于target时，可以让 i 增加；否则，j 减小。

code

class Solution {public:        /**     * @param numbers : Give an array numbers of n integer     * @return : Find all unique triplets in the array which gives the sum of zero.     */    vector
    
     
       > threeSum(vector
      
        &nums) {        // write your code here        int size = nums.size(), target = 0;        if(size < 3) {            return vector
       
        
          >();        }        vector
         
          
            > result; int i = 0, j = 0, k = 0; sort(nums.begin(), nums.end()); for(k=0; k
           
            0 && nums[k]==nums[k-1]) { continue; } for(i=k+1, j=size-1; i
            
             k+1 && nums[i]==nums[i-1]) { i++; continue; } if(j