はじめに

---

与えられたvector<int>& numsの２つの要素の和がint targetになるか答える問題． map<int,int>に{値,インデックス番号}を格納することで、O(NlogN)で計算可能．

全探索による解法もあり、初期の段階で解いた際はこちらで解いが、そちらはO(N^2)となるため推奨しない

問題

---

nums[i] + nums[j] == targetを満たす{i,j}をvector<int>で返す。 入力配列numsには、値の重複が存在しないという制約がある。

コード全体

---

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

解説

---

配列の要素の値をmap<int,int>に格納する。

class Solution {
  public:
  vector<int> twoSum(vector<int>& nums, int target) {
    map<int,int> mp;
    for(int i=0; i<nums.size(); ++i) mp[nums[i]] = i;

配列の各要素に対し、targetとの差が存在するか確認する。

    for(int i=0; i<nums.size(); ++i){
      if( mp.find(target-nums[i]) != mp.end() ){

この時、自身が条件を満たしている場合は無視する（値の重複が無いという前提より）。

        if( mp[target-nums[i]] == i ) continue;

存在する場合：その時のインデックスと対となるインデックスを返す。

        return {i, mp[target-nums[i]]};

全ての要素に対して条件を満たす組が存在しない場合、{-1,-1}を返す。

    return vector<int>(2, -1);
  }
};