1. Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

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

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

思路

题目说只有唯一解。可以采用双重循环暴力求解，但时间复杂度是O(n^2)。

python的解法：

新建一个 dict，对数组中的每个元素 nums[i]，都去查看 dict 中是否有 target - nums[i]，如果有，结束，返回二者的索引，如果没有，将 nums[i] 作为dict的 key，索引作为 value 存入dict中，最多遍历 n 次即可解出，时间复杂度O(n)。

C++解法：

思路和python的解法一样，不过需要新建一个hash表来代替dict。

Python3

#encoding:utf-8
class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        dict = {}
        for i in range(len(nums)):
            if dict.get(target - nums[i], None) == None:
                dict[nums[i]] = i
            else:
                return (dict[target - nums[i]], i)

C++11

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        std::unordered_map<int, int> record;
        for (int i = 0; i < nums.size(); ++i) {
            auto found = record.find(nums[i]);
            if (found != record.end())
                return {found->second, i};
            record.emplace(target - nums[i], i);
        }
        return {-1, -1};
    }
};