乐趣区

关于javascript:15-三数之和leetcodeC语言

jiezi

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

二、双指针法——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
}

  • 工夫复杂度：O(N^2)，其中 NN 是数组 nums 的长度。
  • 空间复杂度：O(logN)。咱们疏忽存储答案的空间，额定的排序的空间复杂度为 O(logN)。然而咱们批改了输出的数组 nums，在理论状况下不肯定容许，因而也能够看成应用了一个额定的数组存储了 nums 的正本并进行排序，空间复杂度为 O(N)。
退出移动版