关于javascript:18-四数之和LeetCodeC语言及JS

一、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().
 */

int cmp(const void *a, const void *b)
{return *((int *)a) - *((int *)b);
}

int **fourSum(int *nums, int numsSize, int target, int *returnSize, int **returnColumnSizes)
{if (numsSize < 4)
  {
    *returnSize = 0;
    *returnColumnSizes = NULL;
    return NULL;
  }
  // 先对数组进行排序
  qsort(nums, numsSize, sizeof(int), cmp);
  // 初始化 *returnSize
  *returnSize = 0;
  // 调配存储四元组的数组
  int **returnArr = (int **)malloc(sizeof(int *) * (numsSize - 2) * (numsSize - 2));
  *returnColumnSizes = (int *)malloc(sizeof(int) * (numsSize - 2) * (numsSize - 2));
  // 开始进入循环
  // 因为进行了剪枝操作，因而，要用 i < numsSize - 3 作为终止循环的条件
  // 否则会导致数组拜访越界
  for (int i = 0; i < numsSize - 3; i++)
  {
    // 剪枝操作
    if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target)
    {break;}
    if (nums[i] + nums[numsSize - 3] + nums[numsSize - 2] + nums[numsSize - 1] < target)
    {continue;}
    // 首元素去重
    if (i > 0 && nums[i] == nums[i - 1])
    {continue;}
    // 因为进行了剪枝操作，因而，要用 j < numsSize - 2 作为终止循环的条件
    // 否则会导致数组拜访越界
    for (int j = i + 1; j < numsSize - 2; j++)
    {
      // 剪枝操作
      if (nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target)
      {break;}
      if (nums[i] + nums[j] + nums[numsSize - 2] + nums[numsSize - 1] < target)
      {continue;}
      // 第二个元素去重
      if (j > i + 1 && nums[j] == nums[j - 1])
      {continue;}
      int head = j + 1;
      int tail = numsSize - 1;
      while (head < tail)
      {
        // 左指针去重
        if (head > j + 1 && nums[head] == nums[head - 1])
        {
          head++;
          continue;
        }
        // 右指针去重
        if (tail < numsSize - 1 && nums[tail] == nums[tail + 1])
        {
          tail--;
          continue;
        }
        if (nums[i] + nums[j] + nums[head] + nums[tail] == target)
        {returnArr[*returnSize] = (int *)malloc(sizeof(int) * 4);
          returnArr[*returnSize][0] = nums[i];
          returnArr[*returnSize][1] = nums[j];
          returnArr[*returnSize][2] = nums[head];
          returnArr[*returnSize][3] = nums[tail];
          (*returnColumnSizes)[*returnSize] = 4;
          (*returnSize) += 1;
          head++;
          tail--;
        }
        else if (nums[i] + nums[j] + nums[head] + nums[tail] > target)
        {tail--;}
        else
        {head++;}
      }
    }
  }
  return returnArr;
}

二、JS 实现

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
const fourSum = function (nums, target) {
  const len = nums.length
  if (len < 4) {return []
  }
  nums.sort((x, y) => {return x - y})
  const results = []
  for (let i = 0; i < len; i++) {if (i > 0 && nums[i - 1] === nums[i]) {continue}
    // 剪枝操作
    if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {break}
    // 剪枝操作
    if (nums[i] + nums[len - 3] + nums[len - 2] + nums[len - 1] < target) {continue}
    for (let j = i + 1; j < len; j++) {if (j > i + 1 && nums[j - 1] === nums[j]) {continue}
      // 剪枝操作
      if (nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {break}
      // 剪枝操作
      if (nums[i] + nums[j] + nums[len - 2] + nums[len - 1] < target) {continue}
      let head = j + 1
      let tail = len - 1
      while (head < tail) {if (head > j + 1 && nums[head - 1] === nums[head]) {
          head++
          continue
        }
        if (tail < len - 1 && nums[tail + 1] === nums[tail]) {
          tail--
          continue
        }
        if (nums[i] + nums[j] + nums[head] + nums[tail] === target) {
          // 存储符合条件的四元组到后果数组
          results.push([nums[i], nums[j], nums[head], nums[tail]])
          // 将头指针右移，尾指针左移
          head++
          tail--
        } else if (nums[i] + nums[j] + nums[head] + nums[tail] > target) {tail--} else {head++}
      }
    }
  }
  return results
}

• 工夫复杂度：O(n^3)，其中 n 是数组的长度。排序的工夫复杂度是 O(nlogn)，枚举四元组的工夫复杂度是 O(n^3)，因而总工夫复杂度为 O(n^3+nlogn)==O(n^3)。
• 空间复杂度：O(logn)，其中 n 是数组的长度。空间复杂度次要取决于排序额定应用的空间。此外排序批改了输出数组 nums，理论状况中不肯定容许，因而也能够看成应用了一个额定的数组存储了数组 nums 的正本并排序，空间复杂度为 O(n)。