【JS】15. 三数之和(leetcode)——C语言

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

阿料发布于 2 月 2 日

一、双指针法——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));

// 开始二重循环,遍历数组nums

for (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;

}

【JS】15. 三数之和(leetcode)——C语言

二、双指针法——JavaScript实现

/**

* @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

}

【JS】15. 三数之和(leetcode)——C语言

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

javascriptc算法leetcode

阅读 51发布于 2 月 2 日

本作品系原创,采用《署名-非商业性使用-禁止演绎 4.0 国际》许可协议

avatar

阿料

一个平凡的coder

1 声望

2 粉丝

0 条评论

得票时间

avatar

阿料

一个平凡的coder

1 声望

2 粉丝

宣传栏

一、双指针法——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));

// 开始二重循环,遍历数组nums

for (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;

}

【JS】15. 三数之和(leetcode)——C语言

二、双指针法——JavaScript实现

/**

* @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

}

【JS】15. 三数之和(leetcode)——C语言

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

以上是 【JS】15. 三数之和(leetcode)——C语言 的全部内容, 来源链接: www.h5w3.com/112705.html

回到顶部