题目链接:https://leetcode.cn/problems/two-sum/
还是只会暴力搜索法,其实也能想到要用空间换时间,但是不知道用啥数据结构比较合适。。。。
仔细想想,就是要把一个数字存到一个能快速搜索的数据结构里,比如target=7,遍历nums{2,3,4}的过程中,遍历到3的时候要能快速找到另外一个数据结构中的数字4,这么看来也就hash table里的key比较合适,正好也能用value保存key对应的数组下标。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
class Solution { public: /* 暴力搜索法 vector<int> twoSum(vector<int>& nums, int target) { for (int i = 0; i < nums.size(); i++) { for (int j = i + 1; j < nums.size(); j++) { if (nums[i] + nums[j] == target) { return {i, j}; } } } return {}; } */ /* 官方hash table搜索法 vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int, int> ht; for (int i = 0; i < nums.size(); i++) { auto it = ht.find(target - nums[i]); if (it != ht.end()) { return {it->second, i}; } else { ht[nums[i]] = i; } } return {}; } */ // 官方hash table解法稍微变化了下,更容易理解一点,但是时间复杂度稍微高一些 vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int, int> ht; for (int i = 0; i < nums.size(); i++) { // 先把数组的数字都丢入hash table ht[nums[i]] = i; } for (int i = 0; i < nums.size(); i++) { // 遍历数组,同时搜索hash table auto it = ht.find(target - nums[i]); if (it != ht.end() && it->second != i) { // 找到跟当前数字nums[i]匹配的另一个目标数字,并且不是当前数字自己 return {i, it->second}; } } return {}; } }; |