# 15. 三数之和(leetcode)——C语言

``/*** 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().*/#include <stdio.h>#include <stdlib.h>#include <stddef.h>int compare(const void *a, const void *b){return *((int *)a) - *((int *)b);}int **threeSum(int *nums, int numsSize, int *returnSize, int **returnColumnSizes){// 数组长度小于3则直接返回空数组if (numsSize < 3){*returnSize = 0;*returnColumnSizes = NULL;return NULL;}// 先对数组进行排序，升序排列，qsort不返回任何值qsort(nums, numsSize, sizeof(int), compare);*returnSize = 0;// 分配存储空间int **returnArr = (int **)malloc(sizeof(int *) * (numsSize - 2) * (numsSize - 2));*returnColumnSizes = (int *)malloc(sizeof(int) * (numsSize - 2) * (numsSize - 2));// 开始二重循环，遍历数组numsfor (int i = 0; i < numsSize; i++){// 如果元素大于0，则其后的元素也大于0，那么三数之和肯定大于0// 所以到此时就可以直接退出遍历了if (nums[i] > 0){break;}// 去除外层循环的重复值if (i > 0 && nums[i] == nums[i - 1]){continue;}// 记录右指针初始下标int third = numsSize - 1;// 记录外层循环下标对应的值，即三元组的第一个元素int oneNum = nums[i];for (int j = i + 1; j < numsSize; j++){// 去除左指针指向的重复值if (j > i + 1 && nums[j] == nums[j - 1]){continue;}// 去除右指针指向的重复的值while (j < third && nums[j] + nums[third] > -oneNum){third--;}// 左右指针重合时，退出内层循环if (j == third){break;}// 将满足条件的三元组保存到结果数组if (nums[j] + nums[third] == -oneNum){returnArr[*returnSize] = (int *)malloc(sizeof(int) * 3);returnArr[*returnSize][0] = oneNum;returnArr[*returnSize][1] = nums[j];returnArr[*returnSize][2] = nums[third];(*returnColumnSizes)[*returnSize] = 3;*returnSize += 1;}}}return returnArr;}int main(void) {int nums[] = {-1, 0, 1, 2, -1, -4};int numsSize = 6;int returnSize;int *returnColumnSizes = NULL;int **returnArr = threeSum(nums, numsSize, &returnSize, &returnColumnSizes);for (int i = 0; i < returnSize; i++) {printf("%d %d %d\n", returnArr[i][0], returnArr[i][1], returnArr[i][2]);}return 0;``}``

``/*** @param {number[]} nums* @return {number[][]}*/const threeSum = function (nums) {const len = nums.length// 数组长度小于3则直接返回空数组if (len < 3) {return []}// 对数组进行排序nums.sort(function (a, b) { return a - b })// 定义一个空数组作为返回数组const returnArr = []for (let i = 0; i < len; i++) {// 如果元素大于0，则其后的元素也大于0，那么三数之和肯定大于0// 所以到此时就可以直接退出遍历了if (nums[i] > 0) {break}// 去除外层循环的重复值if (i > 0 && nums[i] === nums[i - 1]) {continue}// 记录右指针初始下标let third = len - 1// 记录外层循环下标对应的值，即三元组的第一个元素const oneNum = nums[i]for (let j = i + 1; j < len; j++) {// 去除左指针指向的重复值if (j > i + 1 && nums[j] === nums[j - 1]) {continue}// 去除右指针指向的重复的值while (j < third && nums[j] + nums[third] > -oneNum) {third--}// 左右指针重合时，退出内层循环if (j === third) {break}// 将满足条件的三元组push到结果数组if (nums[j] + nums[third] === -oneNum) {returnArr.push([oneNum, nums[j], nums[third]])}}}return returnArr``}``

• 时间复杂度：O(N^2)，其中 NN 是数组nums的长度。
• 空间复杂度：O(logN)。我们忽略存储答案的空间，额外的排序的空间复杂度为O(logN)。然而我们修改了输入的数组nums，在实际情况下不一定允许，因此也可以看成使用了一个额外的数组存储了nums 的副本并进行排序，空间复杂度为 O(N)。

##### 阿料

1 声望

2 粉丝

0 条评论

``/*** 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().*/#include <stdio.h>#include <stdlib.h>#include <stddef.h>int compare(const void *a, const void *b){return *((int *)a) - *((int *)b);}int **threeSum(int *nums, int numsSize, int *returnSize, int **returnColumnSizes){// 数组长度小于3则直接返回空数组if (numsSize < 3){*returnSize = 0;*returnColumnSizes = NULL;return NULL;}// 先对数组进行排序，升序排列，qsort不返回任何值qsort(nums, numsSize, sizeof(int), compare);*returnSize = 0;// 分配存储空间int **returnArr = (int **)malloc(sizeof(int *) * (numsSize - 2) * (numsSize - 2));*returnColumnSizes = (int *)malloc(sizeof(int) * (numsSize - 2) * (numsSize - 2));// 开始二重循环，遍历数组numsfor (int i = 0; i < numsSize; i++){// 如果元素大于0，则其后的元素也大于0，那么三数之和肯定大于0// 所以到此时就可以直接退出遍历了if (nums[i] > 0){break;}// 去除外层循环的重复值if (i > 0 && nums[i] == nums[i - 1]){continue;}// 记录右指针初始下标int third = numsSize - 1;// 记录外层循环下标对应的值，即三元组的第一个元素int oneNum = nums[i];for (int j = i + 1; j < numsSize; j++){// 去除左指针指向的重复值if (j > i + 1 && nums[j] == nums[j - 1]){continue;}// 去除右指针指向的重复的值while (j < third && nums[j] + nums[third] > -oneNum){third--;}// 左右指针重合时，退出内层循环if (j == third){break;}// 将满足条件的三元组保存到结果数组if (nums[j] + nums[third] == -oneNum){returnArr[*returnSize] = (int *)malloc(sizeof(int) * 3);returnArr[*returnSize][0] = oneNum;returnArr[*returnSize][1] = nums[j];returnArr[*returnSize][2] = nums[third];(*returnColumnSizes)[*returnSize] = 3;*returnSize += 1;}}}return returnArr;}int main(void) {int nums[] = {-1, 0, 1, 2, -1, -4};int numsSize = 6;int returnSize;int *returnColumnSizes = NULL;int **returnArr = threeSum(nums, numsSize, &returnSize, &returnColumnSizes);for (int i = 0; i < returnSize; i++) {printf("%d %d %d\n", returnArr[i][0], returnArr[i][1], returnArr[i][2]);}return 0;``}``

``/*** @param {number[]} nums* @return {number[][]}*/const threeSum = function (nums) {const len = nums.length// 数组长度小于3则直接返回空数组if (len < 3) {return []}// 对数组进行排序nums.sort(function (a, b) { return a - b })// 定义一个空数组作为返回数组const returnArr = []for (let i = 0; i < len; i++) {// 如果元素大于0，则其后的元素也大于0，那么三数之和肯定大于0// 所以到此时就可以直接退出遍历了if (nums[i] > 0) {break}// 去除外层循环的重复值if (i > 0 && nums[i] === nums[i - 1]) {continue}// 记录右指针初始下标let third = len - 1// 记录外层循环下标对应的值，即三元组的第一个元素const oneNum = nums[i]for (let j = i + 1; j < len; j++) {// 去除左指针指向的重复值if (j > i + 1 && nums[j] === nums[j - 1]) {continue}// 去除右指针指向的重复的值while (j < third && nums[j] + nums[third] > -oneNum) {third--}// 左右指针重合时，退出内层循环if (j === third) {break}// 将满足条件的三元组push到结果数组if (nums[j] + nums[third] === -oneNum) {returnArr.push([oneNum, nums[j], nums[third]])}}}return returnArr``}``

• 时间复杂度：O(N^2)，其中 NN 是数组nums的长度。
• 空间复杂度：O(logN)。我们忽略存储答案的空间，额外的排序的空间复杂度为O(logN)。然而我们修改了输入的数组nums，在实际情况下不一定允许，因此也可以看成使用了一个额外的数组存储了nums 的副本并进行排序，空间复杂度为 O(N)。