重构求解javascript中的算法

Question

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

给出一组数字(n)找到2个数和,给出(k)并打印它们.
例如

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

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

设置和映射数据结构对于搜索具有O(1)时间复杂度,这使得它们成为良好的数据结构,其中可以利用搜索来提高性能.

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

我搜索总结的数字k,即:(k- num).如果我找到这个数字,我将两个数字都添加到我的结果数据结构中并减value1,以表明它已被使用.

时间复杂度: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))