Return好像没有退出功能

问题描述 投票:0回答:2

现在我正在解决一些 leetcode 问题,我在我的代码中发现了一个奇怪的东西 https://leetcode.com/problems/3sum/ 但我不明白它是如何工作的。

此代码的问题:当在 ThreeSum 函数中使用 hasSimularArray 时,hasSimularArray 中的 Return 不会从函数中退出。问题是 hasSimularArray 一直运行,就好像它是一个递归函数,但事实并非如此。所以当它到达这行代码时“return true;”在 hasSimularArray 中,它必须停止函数中的执行代码。

function threeSum(nums: number[]): number[][] {
  const tripletsResult = [];

  nums.sort((a, b) => a - b);

  for (let i = 0; i < nums.length - 2; i++) {
    let j = i + 1;
    let k = nums.length - 1;
    while (j < k) {
      const possibleResultEl = [nums[i], nums[j], nums[k]];
      const threeNumsSum = nums[i] + nums[j] + nums[k];
      if (threeNumsSum === 0) {
        const hasVal = hasSimularArray(tripletsResult, possibleResultEl);
        if (!hasVal) {
          tripletsResult.push(possibleResultEl);
        }
      } else if (threeNumsSum < 0) {
        j++;
      } else {
        k--;
      }
    }
  }

  return tripletsResult;
}

function hasSimularArray(mainArr: number[][], searchedArr: number[]) {
  if (mainArr.length === 0) {
    return false;
  }

  const searchArrayStr = JSON.stringify([...searchedArr].sort());
  for (let el of mainArr) {
    const elArrayStr = JSON.stringify([...el].sort());
    if (elArrayStr === searchArrayStr) {
      return true;
    }
  }
  return false;
}
console.log(threeSum([0, 3, 0, 1, 1, -1, -5, -5, 3, -3, -3, 0]));

之前我遇到过一个类似的问题,但它的代码有点不同,在嵌套函数中具有相同的返回逻辑,并且该返回以某种方式不仅从嵌套函数退出,而且还从父函数退出。

试图了解调试模式下到底发生了什么,但它没有给我任何线索。

就我而言,当我在没有具有相同值的父函数的情况下单独测试 hasSimularArray 时,情况变得更糟,并且它按预期工作。

有人可以解释一下这里发生了什么吗?

javascript typescript algorithm return
2个回答
0
投票

hasSimularArray 中的返回不会从函数中退出

我不知道你是如何得出这个结论的,但是

return
中的
hasSimularArray
语句没有问题:它们被执行并退出函数。我们可以说这是一个低效函数,但这不是这里的主要问题。

简单的调试表明,当条件

while (j < k)
为真时,您的代码会进入无限
threeNumsSum === 0
。在这种情况下,您不会更改
j
k
的值,因此
while
循环的下一次迭代将查看完全相同的数字并得出相同的结论:
threeNumsSum
为 0,无限地重复这个。

您必须确保

while
循环使窗口
(j, k)
变小。

对于

threeNumsSum
,您既可以增加
j
也可以减少
k
:

      if (threeNumsSum === 0) {
        const hasVal = hasSimularArray(tripletsResult, possibleResultEl);
        if (!hasVal) {
          tripletsResult.push(possibleResultEl);
        }
        // Narrow the window!
        j++; 
        k--;
      }

0
投票

nums
数组很大时,你的算法可能会崩溃。

您可以使用对象(也可以使用映射)有效地跟踪已找到的三元组。您还可以使用同一对象来存储要返回的三元组。

function threeSum(nums: number[]): number[][] {
  const dupeTracker = {};

  nums.sort((a, b) => a - b);

  for (let i = 0; i < nums.length - 2; i++) {
    let j = i + 1;
    let k = nums.length - 1;
    while (j < k) {
      const threeNumsSum = nums[i] + nums[j] + nums[k];
      if (threeNumsSum === 0) {
        const possibleResultEl = [nums[i], nums[j], nums[k]];
        const uniqueKey = JSON.stringify(possibleResultEl.sort());
        if (!dupeTracker[uniqueKey]) {
          dupeTracker[uniqueKey] = possibleResultEl;
        }
      } else if (threeNumsSum < 0) {
        j++;
      } else {
        k--;
      }
    }
  }

  return Object.values(dupeTracker);
}
© www.soinside.com 2019 - 2024. All rights reserved.