■

一個ずつ順番に試すブルートフォースはすぐに思いついた。しかし、これだとO(n²)の時間がかかる。

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とするように発想できるようにならなければ。

1. numsを前から見ていく
2. target-nums[i]になる要素があるか探す
3. 存在するならばそれのindexを返す
4. 存在しないならば、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 {};
    }
};