LeetCode "Two Sum"

#LeetCode

とりあえず一番上にあるやつから解いてみる。

Loading...

問題文

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

与えられた数字列のうち2つを足して、目標の値にする。答えは1通りだけ。数字列内の要素の重複使用はダメ。

探索方法

単純に解こうとすると、1番目の要素を選び、2番目の要素を数列内から全探索する。要するに全探索。

計算量を減らすためには、ハッシュを使って探索時間を削減する。数列内の要素をハッシュのkey、その要素のインデックスをハッシュのvalueとする。最初にハッシュテーブルを作成しておいて、1番目の要素と足し合わせて目標値になる数字がハッシュテーブル内に存在するか？というのを、1番目の要素を変えながら調べていけば良い。

より効率的にするには、ハッシュテーブル作成をしながら、探索をする。具体的には、数列の要素を順に辿り、その要素と足し合わせて目標値になる要素がハッシュテーブル内に存在するかどうかを調べる。存在しなければ、その要素をハッシュテーブルに追加する。

コード

日本語で書いても分かりにくいので、submitしたコードはこちら。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ret = {};
        std::unordered_map<int, int> um = {};
       
        for(auto i = 0u; i < nums.size(); i++){
            auto sub = target - nums[i];
            
            if(um.find(sub) != um.end())
            {
                return {um[sub], i};
            }
            
            um[nums[i]] = i;
        }
        
        throw std::logic_error("cant resolve");
    }
};