c++ - 有没有更有效的方法来检查列表中的两个数字是否相加为 int, k？

Question

我订阅了编码挑战邮件列表。这是今天的:

Given a list of numbers and a number k, return whether any two numbers from the list add up to k.

For example, given[10, 15, 3, 7] and k of 17, return true since 10 + 7 is 17.

Bonus: Can you do this in one pass?

我想到了以下方法，但我想知道这是否是最有效的解决方案。

bool found = false;
int k = 17;
list<int> given({10, 15, 3, 7});

int main() {
    for (int num : given) {
        found = find(given.begin(), given.end(), k - num) != given.end();

        if (found) break;
    }

    return found;
}

代码完美运行。我只想知道它是否可以更有效率或 如果我在我的代码中做任何在工作场所不受欢迎的事情。非常感谢。

Answer 1

您可以使用集合对数组进行一次迭代。

int k = 17;
list<int> given({10, 15, 3, 7});
unordered_set<int> seen();

// O(n) time-complexity
int main() {
    // Iterate over O(n) items
    for (int num : given) {
        // O(1) operations
        if (seen.contains(k - num)) {
            // seen contains a value that is the difference between k and num. If you add num to that value, k - n + n = k, you have found two numbers that sum to k
            return true;
        } else {
            // Better luck next time, keep looking
            seen.add(num);
        }
    }

    return false;
}