哈希 map
思路:遍历数组,用unordered_map记录<nums元素, idx>,然后一边遍历,一边查询unordered_map内是否
已经存在target-元素,如果存在则返回结果索引<“元素i”的位置, “target-元素”的位置>。
注:此题为何不用双指针?因此双指针靠拢一般要排序,但此题最后要返回索引,排序了还咋返回索引。
注:题干存在“找出”关键词,并返回下标,通过这点应该想到哈希map记录。
注:又使用了unordered_map的常见用法,即一边用来“存”“记录元素,idx等”,一般“find”“查询”“target-元素”。
注:for()内再用unordered_map.find()实际上没任何问题,因为哈希结构的unordered_map查询、增删一般是
O(1)复杂度,不会带来影响。
1:元素遍历后插入unordered_map,如果该处放在for()刚开始处,就会出现find()老是查到自己的问题,
比如{3,3},第1个3插入unordered_map后,find()直接把自己找到了,返回{0,0},此时不满足题意,需要注意。
// 复习:此题有巨坑:unmap[nums[i]] = i;放在最后,是屏蔽找到相同的关键。
// 而将其放在最前通过wyh 2 3的方式,则始终有问题,归其原因在于,map的机制,当遇到{3,3}时,第一次遍历map为{3,0},第二次遍历会直接变成{3,1},而非{{3,0},{3,1}},因为不是unordered_multimap(而使用unordered_multimap可能有更多的问题,比如不能unordered_multimap[x]=x等,当前就直接考虑非multi的map即可)。因此,第一次i=0遍历会不通过,第二次i=1遍历也不通过,就退出了。
// 此外,还有一个容易混淆的问题,就是map的find,在找到key后不管满足要求与否,都会直接退出(这也是应该的,因为map不允许多key存在)。
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> unmap;
for (int i = 0; i < nums.size(); i++) {
// unmap[nums[i]] = i; // wyh 3
auto it = unmap.find(target - nums[i]);
// if (it != unmap.end() && i != it->second) { // wyh 2
if (it != unmap.end()) {
return {i, it->second};
}
unmap[nums[i]] = i; // wyh 1
}
return {0, 0};
}
};