C++算法题-Two Sum

题目

Write a function that takes an array of numbers (integers for the tests) and a target number. It should find two different items in the array that, when added together, give the target value. The indexes of these items should then be returned in a tuple / list (depending on your language) like so: (index1, index2).
For the purposes of this kata, some tests may have multiple answers; any valid solutions will be accepted.
The input will always be valid (numbers will be an array of length 2 or greater, and all of the items will be numbers; target will always be the sum of two different items from that array).

示例：

1
2


two_sum({1, 2, 3}, 4); // returns {0, 2} or {2, 0}
two_sum({3, 2, 4}, 6); // returns {1, 2} or {2, 1}

理解起来是提供一列存储整形的数组与目标数，要求在该数组中找到两个相加能等于目标数的元素，并返回在数组中的位置。

1
2
3


std::pair<std::size_t, std::size_t> two_sum(const std::vector<int>& numbers, int target) {
    return {0, 0};
}

题解

双循环

这道题最简单的方法是双循环暴力求解，但是复杂度为 O(n^2)，效率不高

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


std::pair<std::size_t, std::size_t> two_sum(const std::vector<int>& numbers,
                                            int target) {
    int i, j;
    for (i = 0; i < numbers.size(); i++) {
        for (j = i + 1; j < numbers.size(); j++) {
            if (numbers[i] + numbers[j] == target) return {i, j};
        }
    }
    return {-1, -1};
}

思维量少。循环 + 判断，暴力循环

哈希表

使用哈希表结构可以将复杂度降到 O(n)，可谓是效率飞升。
哈希表的作用是存储配对数和在原数组的位置。

1

std::unordered_map<int, std::size_t> counterparts;

只用到一次循环就可以完成目标，关键在于哈希表存储的配对数存储 target - numbers[i] ，也就是该元素距目标还差多少。
那么当如果继续遍历首先要判断的是是否有差数，如果有那么就可以返回了。
要清楚的是 find() 方法返回的是一个迭代器指向找到的那个元素。
如果 it 确实找到了这个元素，那么它返回的就不会是 end() 则可以确认匹配，直接返回。
倘若没有，就把这个数的差值存到 counterparts 内开启新一个循环。

1
2
3
4
5


    for (std::size_t i = 0; i < numbers.size(); ++i) {
        auto it = counterparts.find(numbers[i]);  //查找当前数是否在之前有配对数
        if (it != counterparts.end()) return {it->second, i};  //有这个配对数就返回这个配对数数的位置和目前遍历的位置
        counterparts.emplace(target - numbers[i], i);  //如果没有就把这个数缺了多少和位置存起来
    }

完整代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


std::pair<std::size_t, std::size_t> two_sum(const std::vector<int>& numbers,
                                               int target) {
    std::unordered_map<int, std::size_t> counterparts;  //存储配对数
    for (std::size_t i = 0; i < numbers.size(); ++i) {
        auto it = counterparts.find(numbers[i]);  //查找当前数是否在之前有配对数
        if (it != counterparts.end()) return {it->second, i};  //有这个配对数就返回这个配对数数的位置和目前遍历的位置
        counterparts.emplace(target - numbers[i], i);  //如果没有就把这个数缺了多少和位置存起来
    }
    return {-1, -1};
}