javascript - 重构解决javascript中的算法

Question

我参加了一家开发公司的技术面试。他们问了我以下问题:

Giving an array of numbers (n) find 2 numbers that sum gives (k) and print them.
e.g

Input: n = [2,6,4,5,7,1], k = 8   
Output: result=(2,6),(7,1)   

我的解决方案:

function findSum(n,k){
    let aux = []
    for (let i = 0; i < n.length; i++) {
        for (let j = i+1; j < n.length; j++) {
            if (n[i] + n[j] == k) {
                aux.push({ first: n[i], second: n[j] })
            }
        }
    }
    return aux;
}

他们告诉我，可以使用某种键或映射来进行练习。
有人知道如何只用一个循环来做吗？

Answer 1

以低时间复杂度解决此类问题的关键是能够有效地搜索数据结构。许多答案以优化搜索数组的方式重新排列数组。另一种方法是使用本身具有快速搜索的数据结构。

Set 和 Map 数据结构的搜索时间复杂度为 O(1)，这使它们成为可以利用搜索来提高性能的良好数据结构。

我使用 new Map 并遍历数组，同时将其添加为键。我将 key 设置为数字，将值设置为我看到它的次数。我在 new Set 上使用 map ，因为我还可以跟踪该特定数字的实例数。

我搜索总和为 k 的数字，即:(k - num)。如果找到该数字，我会将这两个数字添加到我的结果数据结构中，并将 value 减 1，以表明它已被使用。

时间复杂度:O(n)，内存复杂度:O(2n)。空间量是原始数组的两倍，因为我有一个 key 和一个 value 要存储在我的 Map

中

function pairSums(arr, k){
    const map = new Map
    const matches = []
    for (let num of arr) {
        const search = k - num 
        if (map.get(search) > 0) {
            matches.push([num, k - num])
            map.set(search, map.get(search) - 1)
        } else if (!map.has(num)){
            map.set(num, 1)
        } else {
            map.set(num, map.get(num) + 1)
        }
    }
    return matches
}

console.log(pairSums([2, 6, 6, 6, 2, 4, 4, 4, 5, 7, 1, 4, 2], 8))