■
一個ずつ順番に試すブルートフォースはすぐに思いついた。しかし、これだとO(n2)の時間がかかる。
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { for(int i = 0; i<nums.size()-1; i++){ for(int j=i+1; j<nums.size(); j++){ if(nums[i]+nums[j] == target){ return {i, j}; } } } return {}; } };
https://leetcode.com/problems/two-sum/discuss/860427/Brute-force-Hash-Table-optimized-hash-table. 高速化で上記URLを真似した。unordered_mapのkeyを1、2、3のindexと考えてしまうが、値の方をindexとするように発想できるようにならなければ。
- numsを前から見ていく
- target-nums[i]になる要素があるか探す
- 存在するならばそれのindexを返す
- 存在しないならば、hashに保存し、次の値に行く
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int, int> hash; for(int i=0; i<nums.size();i++){ if(hash.find(target-nums[i])!=hash.end()){ return {hash[target-nums[i]], i}; } hash[nums[i]] = i; } return {}; } };