H5W3
当前位置:H5W3 > JavaScript > 正文

【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)。

本文地址:H5W3 » 【JS】15. 三数之和(leetcode)——C语言

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址