本文共 1579 字，大约阅读时间需要 5 分钟。

题目：给定一个数组和一个目标值，返回所有不重复的3元组，每个元组的和等于目标值，且元组中，各元素按飞递减顺序。

先对其进行排序，在利用2sum，在2sum中，要求和为0，这里可以将数组中的元素的相反数作为和，找到另外两个数，那么三者的和为0。

在2sum中，经过排序后，总的时间复杂度是排序算法的复杂度占主导O(NlogN)，在查找时是遍历数组，复杂度为O(n)。那么在3sum中，首先进行排序，复杂度为O(NlogN), 在查找时，我们令排序后的数组中的每个元素的相反数作为目标和去调用2sum，整体的复杂度是O(n^2)。当然4sum也可以来调用3sum了，等待。

这里虽然确定了复杂度，但是在具体的实现的时候，需要去瘦身，跳过不可能的解，或者是重复的解，否则超时，真超时。

优化基于两个方面，一种是基于数组元素本身可能存在的重复；一种是基于题目的要求，不要重复的结果。

我们在处理了当前元素后(将当前元素的相反数作为和)，若是下个元素与这个元素相同，那么就不用再去算了；在处理到 i 元素时，i 以前的元素我们也不用考虑了，比如 {1，2，1, 4},要求结果为 4 。 处理 第一个1 时，我们会找到 2,1. 返回{1,1,2},在考虑到第二个1时，得到的一种解还是{1，1，2}, 是一种组合，不是排列。

vector
   
    
      > reUnion;void twoSum(vector
     
       &numbers, int start, int target){	if(numbers.size() == 0 || start >= numbers.size() - 2)		return;	int small = start;	int large = numbers.size() - 1;	while (small < large)	{		int sum = numbers[small] + numbers[large];		bool equal = false;		if(sum == target)		{			vector
      
        re(3);			re[0] = numbers[start - 1];			re[1] = numbers[small];			re[2] = numbers[large];			reUnion.push_back(re);			equal = true;		}		//skip the multiple		if(sum < target || equal)			do 			{				++small;			} while (small  < large && numbers[small] == numbers[small + 1]);		if(sum > target || equal)			do 			{				--large;			} while (large > small && numbers[large] == numbers[large - 1]);	}}vector
       
        
          > threeSum(vector
         
           &num) { if(num.size() < 3) return reUnion; sort(num.begin(),num.end()); for (int i = 0; i < num.size() - 2; ++i) { twoSum(num, i + 1, -num[i]); while(i + 1 < num.size() && num[i + 1] == num[i]) ++i; } return reUnion;}
         
        
       
      
     
    
   

转载地址：http://fglji.baihongyu.com/