LeetCode三数之和——C

灰太狼 2021-10-29 23:54 292阅读 0赞

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

## 题目描述 ##

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。
    例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
    满足要求的三元组集合为：
    [
      [-1, 0, 1],
      [-1, -1, 2]
    ]

## 题解 ##

我认为这道题的难点在于超时，其中有一个例子非常大，容易超时，所以不能暴力求解。  
**双指针求解**  
1、先排序，从小到大排序  
2、选取一个数为标准，另外两个数均在这个数后面（一个i+1、一个末尾），然后对比这个标准。  
3、因为三数之和为0，所以标准必须小于零。  
4、当left<right时循环，求和三种情况

(1)sum<0,left++
    (2)sum>0,right--
    (3)sum==0,符合条件记录三个数值

5、还有难点在于：去重（要符合条件）、分配内存（不能超时）。

## 代码 ##

int\*\* threeSum(int\* nums, int numsSize, int\* returnSize, int\*\* returnColumnSizes)  
**特意说明下，nums表示输入数，numsSize表示有多少个数，returnSize表示返回有几组符合条件数，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** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes)
    {
    	int i = 0;								//当前数值下标
    	int left = i+1;							//左指针
    	int right = numsSize - 1;				//右指针
    	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 < 3 || nums == NULL) {
    		return NULL;
    	}
    
    	quickSort(nums, 0, numsSize - 1);                           //排序
    
    	for (i = 0; i <= numsSize - 3; i++) {
    		left = i + 1;
    		right = numsSize - 1;
    		if (nums[i] > 0) {										// 如果当前数字大于0，则三数之和一定大于0，所以结束循环
    			break;
    		}
    		if (i > 0 && nums[i] == nums[i - 1]) {					// 去重
    			continue;
    		}
    		while (left < right) {
    			sum = nums[i] + nums[left] + nums[right];
    			if (sum > 0) {
    				right--;
    			}
    			else if (sum < 0) {
    				left++;
    			}
    			else {
    				res[*returnSize] = (int*)calloc(3, sizeof(int));
    				res[*returnSize][0] = nums[i];
    				res[*returnSize][1] = nums[left];
    				res[*returnSize][2] = nums[right];
    
    				(*returnColumnSizes)[*returnSize] = 3;
    				(*returnSize)++;
    
    				while (left < right && nums[left] == nums[left + 1]) {		//去除重复的
    					left++;
    				}
    				while (left < right && nums[right] == nums[right - 1]) {
    					right--;
    				}
    				left++; 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<stdlib.h>
    #include<malloc.h>
    
    int main() {
    	int num[] = { -1, 0, 1, 2, -1, -4 };
    	int* nums = (int*)num;
    	int numsSize = sizeof(num) / sizeof(int);
    	int* returnSize = (int*)calloc(1, sizeof(int));
    	//这里的内存分配最大值,即排列组合知识,C几取3
    	//C6取3 == 20
    	int** returnColumnSizes = (int**)malloc(sizeof(int*) * (numsSize * (numsSize - 1) * (numsSize - 2)) / 6);
    	int** res = threeSum(nums, numsSize, returnSize, returnColumnSizes);
    
    	for (int i = 0; i < *returnSize; i++) {				//打印
    		for (int j = 0; j < 3; 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]: https://img-blog.csdnimg.cn/20190818000819450.png?x-oss-process=image/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]: /images/20211029/e2b68e0989464aefb84bda5e25e04954.png