LeetCode #1 Two Sum
Bruce force / AC
什么?这也能AC?可能给大家一点自信吧。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
|
#include <iostream> using namespace std; class { public: vector<int> twoSum(vector<int>& nums, int target) { vector<int>vec; for (int i = 0;i<nums.size();i++){ int temp = nums[i]; for (int j = (i+1);j<nums.size();j++){ if (temp + nums[j] == target){ vec.push_back(i); vec.push_back(j); break; } } } return vec; } };
|
Hash / AC
unordered_map 是STL中一种哈希容器,提供键值对映射,很好用。详询cplusplus reference。
Hash 可以将查找速度降为O(1)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
|
class { public: vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int,int>hashMap; vector<int>vec; for (int i = 0;i<nums.size();i++){ hashMap[nums[i]] = i; } for (int j = 0;j<nums.size();j++){ int diff = target - nums[j]; if (hashMap.find(diff) != hashMap.end() && hashMap[diff] > j) { vec.push_back(j); vec.push_back(hashMap[diff]); break; } } return vec; } };
|
近期评论