Description

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

• input nums[] = [2,7,11,15],target = 9;
• output [0,1]

分析

通过哈希表的O(1)查找性能,在O(n)的时间复杂度内完成查找.

由于构建哈希表和查找哈希表都是O(1)操作,所以总时间复杂度是O(n).

根据题目中的限定条件(有且只有一组解),可以同时完成按数组顺序查找和构建哈希表,对每个元素在它前面的元素列表中查找.

Code

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> map;
        for(int i = 0;i < nums.size();i++)
        {
            unordered_map<int,int>::iterator it = map.find(target-nums[i]);
            if(it!=map.end())
                return vector<int> {it->second, i};
            map[nums[i]] = i;
        }
    }
};