摘要:

对于TwoSum的查找思路进行思考。

要求:

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target,

where index1 must be less than index2. Please note that your returned answers (both index1 and index2)

are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9

Output: index1=1, index2=2

思考:

1. 两数求和, 当遍历的时候，和结果确定, 一个数就已经确定，那么就成为了寻找另一个数的问题
2. 要查找一个特定的数，最快的数据结构就是hash了，这个不难想到
3. 比较有意思的是限定了时间复杂度O(n), 如果事先对所有数据建立一次hash, 这个要耗费的时间也要考虑进去
4. 关键就在于遍历的过程中, 两个数求和，那么这两个数在遍历的过程中都会被遍历到，当第个数被遍历时，两个数都不在hash中，此时可以将第一个数存入hash，以value->index方式存储
5. 那么当第二个数被遍历时，从hash中查找所需的第一个数, 就查询到了
6. 这样的处理便只需要一次遍历

题解:

题解一:

#include <stdio.h>#include <vector>
#include <map>void find(int data[], int len, int target, std::vector<int>& result)
{std::map<int, int> coll;for (int i = 0; i < len; ++i){int value = target - data[i];auto iter = coll.find(value);if (coll.end() == iter){coll.emplace(data[i], i);}else{result.emplace_back(i);result.emplace_back(iter->second);}}
}int main() 
{constexpr int len = 9;int data[len]= {-1,5,4,-2,3,-6,8,7,9};std::vector<int> result;find(data, len, 7, result);size_t size = result.size();// printf("%d\\n", size);for (size_t i = 0; i < size; i+=2){printf("[%d]->%d [%d]->%d\\n", result[i], data[result[i]], result[i+1], data[result[i+1]]);}   return 0;
}