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

k sum：在数组nums中找到k个数相加的和为target，不可重复

这个问题有两个方法：

① double pointer，可以得到O(n^(k-1))

②hash table，得要具体分析一下

2sum：

方法一：

struct num{	int number;	int index;};int* twoSum(int* nums, int numsSize, int target) {	int *ret = (int*)malloc(2 * sizeof(int));	ret[0] = ret[1] = 0;	int j;	struct num *map = (struct num*)malloc(numsSize*sizeof(struct num));	for (j = 0; j
   
     0; increment /= 2){		for (int i = increment; i < numsSize; i++){			struct num tmp = map[i];			for (j = i; j >= increment; j -= increment){				if (tmp.number < map[j - increment].number)					map[j] = map[j - increment];				else					break;			}			map[j] = tmp;		}	}	int fir = 0, sec = numsSize - 1;	while (fir < sec){		if (map[fir].number + map[sec].number == target)		{			if (map[fir].index < map[sec].index)			{				ret[0] = map[fir].index + 1;				ret[1] = map[sec].index + 1;			}			else			{				ret[0] = map[sec].index + 1;				ret[1] = map[fir].index + 1;			}					break;		}		else if (map[fir].number + map[sec].number < target)		{			fir++;		}		else		{			sec--;		}	}	free(map);	return ret;}
   

双指针用while可以写的比较好看，因为要返回的是index，排序之后打乱了，设计一个结构体。

方法二：

int* twoSumI(int* nums, int numsSize, int target) {	int *ret = (int*)malloc(2 * sizeof(int));	ret[0] = ret[1] = 1;	int i = 0, max = 0;	for (; i < numsSize; i++)	{		if (nums[i]>max)			max = nums[i];	}	char *hash = (char*)calloc(2*max+1,sizeof(char));	for (i = 0; i < numsSize; i++)	{		hash[nums[i]+max] ++;	}	for (i = 0; i < numsSize; i++)	{		if (hash[target - nums[i] + max] )		{			if (nums[i] == target / 2 && (hash[target - nums[i] + max]-1))			{				ret[0] = i + 1;				break;			}			else if (nums[i] == target / 2)			{				continue;			}			ret[0] = i + 1;			break;		}	}	i++;//break 使得最后一次i没有自加	for (; i < numsSize; i++)	{		if (nums[i] == target - nums[ret[0] - 1])		{			ret[1] = i + 1;			return ret;		}	}}

C语言实现的一个简单的hash table，因为题目中说有且只有一个解。可以边记录hash边查找，不过还是要遍历找到index，用C++的话比较方便。

方法三：

class Solution {public:	vector
   
     twoSum(vector
    
     & nums, int target) {		map
     
       mapping;		vector
      
        ret;		int i = 0;		while (i
      
     
    
   

3sum：

方法一：

int** threeSum(int* nums, int numsSize, int* returnSize) {	*returnSize = 0;	if (numsSize<3)		return NULL;	int **ret = (int**)malloc(2*numsSize*sizeof(int*));//申请太小，导致run time	int j;	for (int increment = numsSize / 2; increment > 0; increment /= 2){		for (int i = increment; i < numsSize; i++){			int tmp = nums[i];			for (j = i; j >= increment; j -= increment){				if (tmp < nums[j - increment])					nums[j] = nums[j - increment];				else					break;			}			nums[j] = tmp;		}	}	for (int i = 0; i < numsSize - 2 ; i++){		for (int j = i+1; j < numsSize - 1 && nums[i] + nums[j] <= 0; j++){			for (int k = numsSize - 1; k > j && nums[i] + nums[j] + nums[k] >= 0; k--){				if (nums[i] + nums[j] + nums[k] == 0)				{					int *col = (int *)malloc(3 * sizeof(int));					col[0] = nums[i], col[1] = nums[j], col[2] = nums[k];					ret[*returnSize] = col;					(*returnSize)++;				}				while (k - 1>j && nums[k - 1] == nums[k]){					k--;				}			}			while (j + 1 < numsSize && nums[j + 1] == nums[j]){				j++;			}		}		while (i + 1 < numsSize && nums[i + 1] == nums[i]){			i++;		}			}	return ret;}

这是以前写的，也是双指针，写的比较丑，但是逻辑还是挺清晰的~吧

threeSumClosest：

就是要增加一个最接近的判断

int threeSumClosest(int* nums, int numsSize, int target) {	int min = INT_MAX;	int sum = 0;	int ret = 0;	int j;	for (int increment = numsSize / 2; increment > 0; increment /= 2){		for (int i = increment; i < numsSize; i++){			int tmp = nums[i];			for (j = i; j >= increment; j -= increment){				if (tmp < nums[j - increment])					nums[j] = nums[j - increment];				else					break;			}			nums[j] = tmp;		}	}	for (int i = 0; i < numsSize - 2; i++){		int j = i + 1, k = numsSize - 1;		while (j < k){			sum = nums[i] + nums[j] + nums[k];			if (sum == target)				return sum;			else if (sum < target)			{				j++;			}			else			{				k--;			}			if (target>sum && min>target - sum)			{				min = target - sum;				ret = sum;			}			else if (target
   
    sum - target)			{				min = sum - target;				ret = sum;			}		}		while (i + 1 < numsSize && nums[i + 1] == nums[i]){			i++;		}	}	return ret;}
   

4sum:

方法一：

int** fourSum(int* nums, int numsSize, int target, int* returnSize) {	*returnSize = 0;	int **ret = (int **)malloc(numsSize * numsSize*sizeof(int*));	int sum = 0;	int j;	for (int increment = numsSize / 2; increment > 0; increment /= 2){		for (int i = increment; i < numsSize; i++){			int tmp = nums[i];			for (j = i; j >= increment; j -= increment){				if (tmp < nums[j - increment])					nums[j] = nums[j - increment];				else					break;			}			nums[j] = tmp;		}	}	//i,l,j,k	for (int i = 0; i < numsSize - 3; i++){		for (int l = i + 1; l < numsSize - 2; l++){			int j = l + 1, k = numsSize - 1;			while (j < k){				sum = nums[i] + nums[l] + nums[j] + nums[k];				if (sum == target)				{					int *col = (int *)malloc(4 * sizeof(int));					col[0] = nums[i], col[1] = nums[l], col[2] = nums[j],col[3]=nums[k];					ret[*returnSize] = col;					(*returnSize)++;										while (j + 1 < numsSize && nums[j + 1] == nums[j]){						j++;					}					while (k - 1 > j && nums[k - 1] == nums[k]){						k--;					}					j++;					k--;				}				else if (sum < target)				{					j++;				}				else				{					k--;				}			}			while (l + 1 < numsSize && nums[l + 1] == nums[l]){				l++;			}		}			while (i + 1 < numsSize && nums[i + 1] == nums[i]){			i++;		}	}	return ret;}

方法二：

class SolutionI {public:	vector
   
    
     > fourSum(vector
     
      & nums, int target) {		int i, j;		unordered_map
      
       >> map;		vector
       
        
         > ret; if (nums.size() < 4) return ret; for (i = 0; i < nums.size(); i++){ for (j = i+1; j < nums.size(); j++){ pair
         
           index(i, j); map[nums[i] + nums[j]].push_back(index); } } for (auto i = map.begin(); i != map.end();i++){ if (map.find(target - i->first) != map.end()) { for (auto j = (i->second).begin(); j != (i->second).end(); j++){ for (auto k = map[target - i->first].begin(); k != map[target - i->first].end(); k++){ if (j->first != k->first && j->first != k->second && j->second != k->first && j->second != k->second){ vector
          
            four = { nums[(j->first)], nums[j->second], nums[k->first], nums[k->second] }; sort(four.begin(), four.end()); ret.push_back(four); } } if (i->first == target - i->first) { break; } } } } sort(ret.begin(), ret.end()); auto tmp = unique(ret.begin(), ret.end()); ret.erase(tmp,ret.end()); return ret; } };
          
         
        
       
      
     
    
   

把四个数分成两个数，将复杂度降为O(n^2)，但是AC的时间是240s，有没有知道 c++ AC中快的是如何实现的呀？？？有个网友也是类似这样的，map记录和检查是否存在放在一起，可是就是超时，不知道为什么，把他的程序也粘出来：

转自：https://leetcode.com/discuss/26678/please-help-why-it-is-time-limit-exceeded-on-this-4sum-problem?show=26678#q26678  

TLE

class Solution {public:    vector
   
    
      > fourSum(vector
     
       &num, int target) {        vector
      
       
        > rt;        set
        
         
          > mset; int n = num.size(); if (n<4) return rt; unordered_map