题目:

给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0
且不重复的三元组。
注意:答案中不可以包含重复的三元组。

示例1:

输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]

示例2:

输入:nums = []
输出:[]

示例3:

输入:nums = [0]
输出:[]

提示:

0 <= nums.length <= 3000
- 1 0 5 10^5 105 <= nums[i] <= 1 0 5 10^5 105

解题代码:
/** * Return an array of arrays of size *returnSize. * The sizes of the arrays
are returned as *returnColumnSizes array. * Note: Both returned array and
*columnSizes array must be malloced, assume caller calls free(). */ void exch(
int *x, int *y) { int temp = *x; *x = *y; *y = temp; } int getIndex(int arr[],
int left, int right) { int refer = arr[left]; int index = left; while(left <
right) { while((arr[right] > refer) && (left < right)) right--; while((arr[left]
<= refer) && (left < right)) left++; exch(&arr[left], &arr[right]); } exch(&arr[
left], &arr[index]); return left; } int quickSort(int arr[], int left, int right
) { if(left < right) { int index = getIndex(arr, left, right); quickSort(arr,
left, index - 1); quickSort(arr, index + 1, right); } return 0; } // 上边是快速排序代码
int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes
){ // 上来就要给returnSize赋值 用来表示返回结果的行数 它应该是用来遍历数组的 // 如果写在return NULL之后
returnSize没有值当遍历的时候就会报错 *returnSize = 0; if(numsSize < 3) return NULL; // 将数组排序
双指法的前提就是排序 quickSort(nums, 0, numsSize - 1); // 用来规划内存 int size = numsSize; //
分配内存 returnSize指针指向常量 所以不用malloc // retNums存储最后返回的结果 int ** retNums = (int **)
malloc(sizeof(int *) * size); // returnColumnSizes 存储retNums 每一列的大小 *
returnColumnSizes= (int *)malloc(sizeof(int *) * size); for(int i = 0; i <
numsSize; i++){ // 判断当前基准值是否前边已经算过了 如果算过直接进行下一次循环 if(i > 0 && nums[i] == nums[i-
1]) continue; // 三数之和等于0 必有负数 所以当基准值大于0时后边就没要继续执行了 if(nums[i] > 0) break; int
left= i + 1; int right = numsSize - 1; while(left < right){ int sum = nums[i] +
nums[left] + nums[right]; if(sum == 0){ // 这里的两个while循环也是为了去重 while(left < right
&& nums[left] == nums[left + 1]){ left++; continue; } while(left < right && nums
[right] == nums[right - 1]){ right--; continue; } // 将三个数存入数组 retNums[*
returnSize] = (int *)malloc(sizeof(int) * 3); // 因为是三数之和 所以二维数组retNums的每一列都是3
感觉用一维存储就可以 二维有点鸡肋 难道是用来提高难度? (*returnColumnSizes)[*returnSize] = 3; retNums[*
returnSize][0] = nums[i]; retNums[*returnSize][1] = nums[left++]; retNums[*
returnSize][2] = nums[right--]; *returnSize += 1; // 灵魂代码 重新规划内存大小为原来的2倍 if(*
returnSize>= size){ size = size * 2; retNums = (int **)realloc(retNums, sizeof(
int *)*size); *returnColumnSizes = (int *)realloc(*returnColumnSizes, sizeof(int
*) * size); } }else if(sum > 0) // 如果三数之和大于0说明正数太大了 那就要将right-- right--; else
// 小于0说明负数太小了 那就要left++ left++; } } return retNums; }

顺便一提:我一直以为returnColumnSizes是要返回的数组,直到提交数次不通过后,才发现事情不对,囧

realloc还是很有用的,大概节省了10MB的空间,快速排序可以不用自己写,直接调用qsort就可以了,用qsort执行了一遍,跟我自己写的快排时间一样,看来我快排写的还不错

技术
©2019-2020 Toolsou All rights reserved,
大一上c语言学生管理系统(下)年底了,不要跳槽。字节跳动测试工程师凉经分享教你用Python画一棵圣诞树用C实现圣诞树python 使用turtle 画樱花(python3验证ok)win10系统的计算机C盘在哪,c盘users在哪(win10c盘找不到users)计算机发展史上最著名的两位鼻祖HDFS主要组件(数据块、NameNode、DataNode、secondaryNameNode)python 指定时间运行代码