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

在做三数之和的时候我们可以通过锁定一个数字，在进行左界右界的确定，在确定的范围中，寻找这个数字，那么我们将之泛化到四数之和中，既然三数之和我们确定了一个数字，那么在四数之和中，我们确定两个数字。锁定两个数字之和，确定左界和右界对范围内搜索。ok，思路明确，我们考虑特殊情况。

先对数组排序，使之为升序，这里可以使用冒泡，快排，选排，等等，任意选择。

• 我们考虑，如果我们目前遍历到的数字，从第i个开始，往后三个共四个数字相加，若是大于目标值，那么很明显，这个数组中已经找不到更小的组合了，因此直接返回空。
• 假设我们已经锁定第一个数字，而我们的确定的右界，第n个，第n-1个，第n-2个数字，与第一个数字相加，已经小于了target，那么很明显我们直接跳过这次循环，让这个数字走向更大的数字才可以搜索得到。
• 我们需要考虑去重的问题，排序之后重复的数字都是在一块的，因此我们只要判断上一次锁定的是否与这一次一样，若一样就跳过。
• 这样我们就找到了两个continue的条件和一个break的条件。
• 在锁定第二个数字的遍历过程中，我们同样重复以上的过程，那么我们就可以避免很多次无用的迭代。

c代码：

/*力扣 四数之和 c by ksks14 2020/11/10 13:31*//*思路，快排后利用双指针双面夹击，在思路上与三数之和几乎一样*/#define maxsize 2000int compare(const void* a, const void* b) {
       return *(int*)a - *(int*)b;}int** fourSum(int* nums, int numsSize, int target, int* returnSize, int** returnColumnSizes){
   	int **answer=(int**)malloc(sizeof(int*)*maxsize);	*returnColumnSizes=(int*)malloc(sizeof(int)*maxsize);	*returnSize=0;//初始化需要的变量	if(numsSize<4)//判断特殊情况 		return answer;	qsort(nums,numsSize,sizeof(int),compare);	for(int i=0;i
   
    0&&nums[i]==nums[i-1])||(nums[i]+nums[numsSize-3]+nums[numsSize-2]+nums[numsSize-1]
    
     target)//求前四个数之和，若是大于target则根本没有符合的数字 			break;		//考虑两种特殊情况 		for(int j=i+1;j
     
      i+1&&nums[j]==nums[j-1])||(nums[i]+nums[j]+nums[numsSize-2]+nums[numsSize-1]
      
       target)				break;			int l=j+1,r=numsSize-1;			while(l
       
        l&&nums[r]==nums[r-1])						r--;					l++,r--;				}				else if(target>nums[i]+nums[j]+nums[l]+nums[r]) l++;				else r--;			}		}	}	return answer;}
       
      
     
    
   

python代码：(python思路与c相同，因此我借用网友代码，懒得动手😂)

class Solution:    def fourSum(self, nums, target):        ans = []        nums.sort()        len_nums = len(nums)        table = {val: index for index, val in enumerate(nums)}        # 枚举前三个数        for i in range(len_nums-3):            if i > 0 and nums[i] == nums[i-1]:                continue            if nums[i] * 4 > target:                break            if nums[i] + 3 * nums[-1] < target:                continue            for j in range(i + 1, len_nums-2):                if j > i + 1 and nums[j] == nums[j-1]:                    continue                if nums[i] + 3*nums[j] > target:                    break                if nums[i] + nums[j] + 2*nums[-1] < target:                    continue                for k in range(j + 1, len_nums-1):                    if k > j + 1 and nums[k] == nums[k - 1]:                        continue                    key = target - nums[i] - nums[j] - nums[k]                    if table.get(key, -1) > k:                        ans.append([nums[i], nums[j], nums[k], key])#key已经成为我们需要的值了

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