Two Sum：给出一个整数数组，返回两个数的下标值，令其和等于一个指定的目标值 #Leetcode

// Given nums = [2, 7, 11, 15], target = 9,

// Because nums[0] + nums[1] = 2 + 7 = 9,

// return [0, 1].

#include <iostream>

#include <vector>

int GetIndexByValue(const std::vector<int> &inArr, int value, int startIndex) {

    for (int i = startIndex; i < inArr.size(); ++i) {

        if (value == inArr[i]) {

            return i;

        }

    }

    return -1;

}

std::vector<int> GetIndicesOf2Addons(const std::vector<int> &inArr, int target) {

    for (int i = 0; i < inArr.size(); ++i) {

        int _2ndAddon = target - inArr[i];

        int indexOf2ndAddon = GetIndexByValue(inArr, _2ndAddon, i + 1);

        if (indexOf2ndAddon < 0) {

            std::cout << "Failed to find: " << _2ndAddon << "\n";

            continue;

        }

        return std::vector<int> {i, indexOf2ndAddon};

    }

    return std::vector<int>(0);

}

int main(int argc, char const *argv[]) {

    std::vector<int> nums {

        2, 3, 11, 15, -2

    };

    int target = 4;

    std::vector<int> result = GetIndicesOf2Addons(nums, target);

    if (result.empty()) {

        std::cout << "Failed.\n";

        return -1;

    }

    for (auto i: result) {

        std::cout << i << "\t";

    }

    std::cout << "\n";

    return 0;

}

// g++ two_sum.cpp -std=c++11 && ./a.out

参考，https://cloud.tencent.com/developer/article/1010478，使用hash_map或者unordered_map实现：

// Given nums = [2, 7, 11, 15], target = 9,

// Because nums[0] + nums[1] = 2 + 7 = 9,

// return [0, 1].

#include <iostream>

#include <vector>

#include <unordered_map>

class Solution {

public:

    std::vector<int> twoSum(std::vector<int> &numbers, int target) {

        // Key is the number and value is its index in the std::vector.

        std::unordered_map<int, int> hash;

        for (int i = 0; i < numbers.size(); i++) {

            int numberToFind = target - numbers[i];

            // if numberToFind is found in map, return them

            if (hash.find(numberToFind) != hash.end()) {

                return std::vector<int> {i, hash[numberToFind]};

            }

            // number was not found. Put it in the map.

            hash[numbers[i]] = i;

        }

        return std::vector<int>(0);

    }

};

int main(int argc, char const *argv[]) {

    std::vector<int> nums {

        2, 3, 11, 15

    };

    int target = 0;

    Solution sol;

    std::vector<int> res = sol.twoSum(nums, target);

    if (res.empty()) {

        std::cout << "Failed.\n";

        return -1;

    }

    for (auto i: res) {

        std::cout << i << "\t";

    }

    std::cout << "\n";

    return 0;

}

// g++ two_sum.cpp -std=c++11 && ./a.out

算法本身遍历一次，花费了 O(n) 的时间复杂度，遍历过程中的 find() 方法本身花费 O(log n)，所以该算法总时间复杂度为 O(nlog n)。

Two Sum：给出一个整数数组，返回两个数的下标值，令其和等于一个指定的目标值 #Leetcode的相关教程结束。