1 Two Sum

题目

1 Two Sum

题解

最简单的方法就是直接暴力求解，时间复杂度为\(O(n^2)\)，空间复杂度\(O(1)\)。

如果想要速度更快的话，可以使用map容器（数据结构中的哈希表）。遍历每个元素，记subtract为目标数字减当前元素数字的结果，把每个元素的subtract及其对应的下标写入map中，一旦当前元素的数字在map中出现过，立刻返回map中对应数字的下标和当前元素的下标。

使用哈希表虽然可以把时间复杂度降为\(O(n)\)，但空间复杂度会升为\(O(n)\)。这是一种用空间换时间的做法。

代码

#include <vector>
#include <map>

using namespace std;

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