return好像没有退出函数

Question

现在我正在解决一些 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 时，情况变得更糟，并且它按预期工作。

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

Answer 1

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--;
      }

Answer 2

当

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);
}