LeetCode四数之和——C

古城微笑少年丶 2021-10-30 07:16 262阅读 0赞

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/4sum

## 题目描述 ##

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：  
答案中不可以包含重复的四元组。

示例：
    给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
    满足要求的四元组集合为：
    [
      [-1,  0, 0, 1],
      [-2, -1, 1, 2],
      [-2,  0, 0, 2]
    ]

## 题解 ##

其实这道题和前面的三数之和，最接近的三数之和类似，都用到双指针求解，只是四树之和双指针时需要固定两个数值，后面两个遍历。

## 代码 ##

int\*\* fourSum(int\* nums, int numsSize, int target, int\* returnSize, int\*\* returnColumnSizes)  
**需要输入指针数值，指针大小，目标值，返回值大小，返回列大小（搞不懂为什么是二级指针）**

void quickSort(int* nums, int first, int end) {					//快速排序 
    	int temp, l, r;
    	if (first >= end) {
    		return;
    	}
    	temp = nums[first];
    	l = first;
    	r = end;
    	while (l < r) {
    		while (l < r && nums[r] >= temp) {
    			r--;
    		}
    		if (l < r) {
    			nums[l] = nums[r];
    		}
    		while (l < r && nums[l] <= temp) {
    			l++;
    		}
    		if (l < r) {
    			nums[r] = nums[l];
    		}
    	}
    	nums[l] = temp;
    	quickSort(nums, first, l - 1);
    	quickSort(nums, l + 1, end);
    }
    
    int** fourSum(int* nums, int numsSize, int target, int* returnSize, int** returnColumnSizes) {
    	int sum = 0;							//和
    	int base_alloc_size = 16;				//基本内存
    	int** res = (int**)malloc(sizeof(int*) * base_alloc_size);
    	(*returnSize) = 0;
    	*returnColumnSizes = (int*)malloc(sizeof(int) * base_alloc_size);
    
    	if (numsSize < 4 || nums == NULL) {
    		return NULL;
    	}
    
    	quickSort(nums, 0, numsSize - 1);                          			//排序
    
    	for (int i = 0; i < numsSize - 3; i++) {
    		if (i > 0 && nums[i] == nums[i - 1]) {							//去重
    			continue;
    		}
    		for (int j = i + 1; j < numsSize - 2; j++) {
    			if (j > i + 1 && nums[j] == nums[j - 1]) {					//去重
    				continue;
    			}
    			int left = j + 1;
    			int right = numsSize - 1;
    			while (left < right) {
    				sum = nums[i] + nums[j] + nums[left] + nums[right];
    				if (sum == target) {
    					res[*returnSize] = (int*)malloc(sizeof(int) * 4);
    					res[*returnSize][0] = nums[i];
    					res[*returnSize][1] = nums[j];
    					res[*returnSize][2] = nums[left];
    					res[*returnSize][3] = nums[right];
    
    					(*returnColumnSizes)[*returnSize] = 4;
    					(*returnSize)++;
    
    					while (left < right && nums[left] == nums[left + 1]) {		//去重
    						left++;
    					}
    					left++;
    				}
    				else if (sum < target) {
    					left++;
    				}
    				else {
    					right--;
    				}
    
    				if (*returnSize == base_alloc_size) {							//空间不足，扩充内存
    					base_alloc_size = base_alloc_size * 2;
    					res = (int**)realloc(res, base_alloc_size * sizeof(int*));
    					(*returnColumnSizes) = (int*)realloc((*returnColumnSizes), base_alloc_size * sizeof(int));
    				}
    			}
    		}
    	}
    	return res;
    }

## 调试 ##

#include<stdio.h> 
    #include<malloc.h>
    
    int main() {
    	int num[] = { 1, 0, -1, 0, -2, 2 };
    	int* nums = (int*)num;
    	int numsSize = sizeof(num) / sizeof(int);
    	int target = 0;
    	int* returnSize = (int*)malloc(sizeof(int) * 1);
    	//这里的内存分配最大值,即排列组合知识,C几取3
    	//C6取3 == 20
    	int** returnColumnSizes = (int**)malloc(sizeof(int*) *  1);
    	int** res = fourSum(nums, numsSize, target, returnSize, returnColumnSizes);
    
    	for (int i = 0; i < *returnSize; i++) {				//打印
    		for (int j = 0; j < 4; j++) {
    			printf("%d ", res[i][j]);
    		}
    		printf("\n");
    	}
    	return 0;
    }

## 结果 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70]: /images/20211029/89a7a24680af41f38cf9a415d5ac4a7d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 1]: /images/20211029/993ea693756544f58cd05b639d19b8d5.png