本文共 1843 字，大约阅读时间需要 6 分钟。

题目

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.

Example:

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

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

return [0, 1]. UPDATE (2016/2/13): The return format had been changed to zero-based indices. Please read the above updated description carefully.

解答

用一个unordered_map的结构来存储numbers，其中key是nums中的元素，value是nums中该元素对应的下标。

由于unordered_map是基于hash表来实现的，所以其查找时间复杂度为O(1)。 但是先要存储，时间为O(N)。

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

如果成立，表明numberToFind是在hash里面。即找到了另外一个数字。

如果上面代码不成立，即numberToFind不在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()) {                    //+1 because indices are NOT zero based            result.push_back(hash[numberToFind] + 1);            result.push_back(i + 1);                        return result;        }            //number was not found. Put it in the map.        hash[numbers[i]] = i;**

整个代码

vector
   
     twoSum(vector
    
      &numbers, int target){    //Key is the number and value is its index in the vector.    unordered_map
     
       hash;    vector
      
        result;    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()) {                    //+1 because indices are NOT zero based            result.push_back(hash[numberToFind] + 1);            result.push_back(i + 1);                        return result;        }            //number was not found. Put it in the map.        hash[numbers[i]] = i;    }    return result;}
      
     
    
   

转载地址：http://aexvi.baihongyu.com/