一个常见的编码面试问题

大家好！欢迎回到“代码审查”系列面试挑战，每周发布一次，完全免费供社区使用。本周我们将探讨一个常见且相对简单的问题，我个人在面试中也多次被问到过这个问题。我之所以选择这个挑战，是因为有多种方法可以解决这个问题，每种方法在时间和空间上都有不同的权衡。

挑战：

编写一个函数FindIntersection，读取一个包含两个元素的字符串数组：第一个元素表示按升序排列的逗号分隔数字列表，第二个元素表示另一个按排序的逗号分隔数字列表。你的目标是返回一个按排序顺序出现在输入数组两个元素中的数字字符串。如果没有交集，则返回字符串"false"。

例如：如果输入数组是，则["1, 3, 4, 7, 13", "1, 2, 4, 13, 15"]输出字符串应该是，"1, 4, 13"因为这些数字在两个字符串中都出现了。给定的数组不会为空，并且数组中的每个字符串都是按升序排列的数字，并且可能包含负数。

暴力破解方法：

一种强力的解决方案是循环遍历第一个字符串中的数字，然后针对第一个字符串中的每个数字，循环遍历另一个字符串中的所有数字，寻找匹配项。如果找到匹配项，则将该值连接到结果字符串。

function FindIntersection (strArr) {
  const inBothStrings = []
  const arr1 = strArr[0].split(', ')
  const arr2 = strArr[1].split(', ')
  arr1.forEach(elementArr1 => {
    const numArr1 = parseInt(elementArr1)
    arr2.forEach(elementArr2 => {
      const numArr2 = parseInt(elementArr2)
      if (numArr1 === numArr2) {
        inBothStrings.push(numArr1)
      }
    })
  })
  return inBothStrings.join(',')
}

虽然这可行，但并非最优解。最坏的情况（如果没有匹配）是，对于第一个字符串中的每个元素，我们都必须遍历第二个字符串中的每个元素。这具有时间复杂度，O(nm)其中n和m是给定字符串的大小。

如果你还没听说过大 O 符号，不妨看看这篇很棒的文章，它详细介绍了所有细节。理解大 O 符号，并能够向面试官清晰地表达你的解决方案的最优性，是任何技术面试中极其重要的一环。

尝试一下：

前往Coderbyte，尝试以更优化的方式解决这个问题。记得下周回来，我会讨论一些其他解决方案以及这个问题的常见陷阱。祝你编程顺利 :)

我们的时事通讯📫

每次发布重大功能时，我们都会发布一小段功能揭秘，以便我们的社区能够第一时间获悉我们的新动态。请在此处提供您的电子邮件地址，我们会将您添加到“第一时间知晓”列表中 :)