LeetCode: 1. Two Sums

問題の要約

整数配列から足したらnになる要素を２つ探し、そのインデックスを返す

問題

問題へのリンク

回答１　全探索

まずは、総当たりの回答を作成。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        for(int i=0; i<nums.size(); i++) {
            for(int j=1; j<nums.size(); j++) {
                if(i!=j && nums[i]+nums[j]==target){
                    return {i,j};
                }
            }
        }
        return {-1};
    }
};

時間計算量: O(N^2) 、空間計算量:O(1)

全探索でも提出すると意外とAccepted されました。
でも Runtime=268 ms、Memor=9 MB と実行時間が多めな結果になりました。

回答２　unordered_map

次に、ハッシュマップを使うことにしました。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> hashMap ;
        for(int i=0; i<nums.size();i++) {
            hashMap[nums[i]] = i;
        }
        
        for(int i=0; i<nums.size();i++) {
            if( i != hashMap[target-nums[i]] &&
                hashMap[target-nums[i]] != 0) {
                return {i, hashMap[target-nums[i]]};
            } 
        }
        return {-1};
    }
};

時間計算量: O(N) 、空間計算量:O(1)

提出すると、Runtime=12 ms、Memory=11.1 MB と早くなりました。
回答１に比べて 22倍の速度を達成しました。