Hackerrank带回家测试：JS函数栈溢出及超时问题排查

嘿，我一眼就揪出你代码里的致命问题了——这根本不是时间复杂度需要优化的事儿，是一个低级笔误导致的无限死循环！

看你这段内层循环的代码：

for(let j = 0; j < phrases.length; i++){ // 此处存在笔误，应为j++，会导致死循环

你把内层循环的迭代变量写成i++了！原本应该是j++来让内层循环正常遍历所有短语，但现在每次内层循环都会让外层循环的i不断递增，而j永远停在0的位置：

• 内层循环的终止条件j < phrases.length永远满足（因为j一直是0）
• 外层循环的i会越来越大，永远不会走到退出条件i < phrases.length

这就导致你的程序会无限运行下去——不管输入多小，都会一直循环，所以Python Tutor触发1000步限制、Repl卡顿、Hackerrank超时都是这个原因。

先修复死循环的代码 #

把内层循环的i++改成j++，修复后的函数：

function generate_phrases(phrases) {
 const result = [];
 for(let i = 0; i < phrases.length; i++){
  let sub1 = phrases[i].split(' ');
  for(let j = 0; j < phrases.length; j++){ // 这里改成j++
   let sub2 = phrases[j].split(' ');
   if(sub1[sub1.length-1] === sub2[0]){
    let string = sub1.concat(sub2.slice(1)).join(' ');
    result.push(string);
   }
  }
 }
 return result;
}

现在用你给的测试输入运行，就能得到和预期一致的输出了。

额外：关于时间复杂度优化（可选） #

如果之后要处理更大规模的输入，当前的O(n²)复杂度确实可以优化：

• 提前预处理所有短语，用一个哈希表（比如Map）存储：键是短语的首词，值是所有以这个词开头的短语列表
• 然后遍历每个短语，取它的尾词，去哈希表里找对应的短语，直接拼接生成结果
  这样就能把复杂度降到O(n)（预处理）+ O(m)（m是匹配到的短语对数），效率会高很多。

比如优化后的示例思路：

function generate_phrases(phrases) {
  const headMap = new Map();
  // 预处理：按首词分组
  phrases.forEach(phrase => {
    const words = phrase.split(' ');
    const head = words[0];
    if (!headMap.has(head)) {
      headMap.set(head, []);
    }
    headMap.get(head).push(words.slice(1)); // 存首词之后的部分
  });

  const result = [];
  phrases.forEach(phrase => {
    const words = phrase.split(' ');
    const tail = words[words.length - 1];
    // 找所有以tail为首词的短语后缀
    if (headMap.has(tail)) {
      headMap.get(tail).forEach(suffix => {
        result.push([...words, ...suffix].join(' '));
      });
    }
  });
  return result;
}

不过现在你的核心问题是死循环，先修复这个笔误，所有小测试用例就能正常通过了！

内容的提问来源于stack exchange，提问作者DBN