LeetCode 1. Two Sum

10来年没写博客了，这次主要是为了撸题并且能找到地方记下来。这是第一题。

地址在这里：https://leetcode.com/problems/two-sum/?tab=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:

Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].

刚开始的想法非常不靠谱，就是穷举，结果是最慢的0.17%，丢人啊，就不提了。

后来第二个想法还是不错的，简单来说就是：

首先是第一个数字2，那么就要寻找整个数组里有没有9-2=7，所以最好就是创建一个map，key是数字，value是一个vector，保存这个数字的所有索引信息。注意这里有个小陷阱，如果target=8，而数字中有两个4，那么这个情况需要特殊处理下。

代码如下：

vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int, vector<int>> smap; for (int i = 0; i < nums.size(); ++i) smap[nums[i]].push_back(i); vector<int> res; for (auto mit : smap) { int val = target - mit.first; if (val == mit.first) { if (mit.second.size() == 2) return mit.second; continue; } auto it = smap.find(val); if (it != smap.end()) { res.push_back(*mit.second.begin()); res.push_back(*it->second.begin()); break; } } return res; }

这段代码运行时间9ms，超过了60.05%的人，勉强算过关吧。