1. Two Sum
精彩评论
有人相爱，有人夜里开车看海，有人leetcode第一题都做不出来。
方法一：暴力枚举
class Solution { public: vector<int> twoSum(vector<int> &nums, int target) { for (int i = 0; i < nums.size(); i++) { int div = target - nums[i]; for (int j = i + 1; j < nums.size(); j++) { if (div == nums[j]) { return {i, j}; } } } return {}; } };
方法二：哈希表
暴力解法的时间复杂度过高，考虑使用一种方法将遍历过的信息存储起来，可以选择哈希表的方式，以空间换时间。可以先查询哈希表里是否存在target-x，如果不在就存进去，找到了就返回下标。
class Solution { public: vector<int> twoSum(vector<int> &nums, int target) { unordered_map<int, int> hashtable; for (int i = 0; i < nums.size(); i++) { int cut = target - nums[i]; auto it = hashtable.find(cut); if (it != hashtable.end()) { return {it->second, i}; } else { hashtable[nums[i]] = i; } } return {}; } };
总结
只会暴力是没救的
