LeetCode：TwoSum Solution

Question

私は、この回答のアルゴリズムを作るためにマップを使用しようとしていますhttps://leetcode.com/problems/two-sum/#/description O（n）、しかし何らかの理由で私は多くのテストケースに対して不適切なインデックスを取得しています。試してみてください

私が知る限り、私はイテレータを適切にチェックしていますが、これは私には新しいものです。私が望む正しいインデックスを返すのかどうかは完全にはわかりません。

//My Code: 



#include <iostream> 
#include <cstdio> 
#include <array> 
#include <vector> 
#include <map> 

std::vector<int> twoSum(int nums[], int size, int target) 
{ 
    std::vector<int> answer; 
    std::map<int, int> myMap; 
    std::map<int, int>::iterator it; 
    std::cout << size << std::endl; 
    for (int i = 0; i < size; i++) 
    { 
     myMap.insert(std::pair<int, int>(nums[i], i)); 
     int indexItOne = distance(myMap.begin(), myMap.find(nums[i])); 
     int indexItTwo = distance(myMap.begin(), myMap.find(target-nums[i])); 
     it = myMap.find(target - nums[i]); 

     if (it != myMap.begin() || indexItOne != indexItTwo) 
     { 
      answer.push_back(i); 
      answer.push_back(distance(myMap.begin(), myMap.find(target - nums[i]))); 
      return answer; 
     } 

    }//for 

}//twoSum 

Answer 1

マップはnumからそのnumのインデックスにマッピングする必要がありますが、それはすぐにマップに挿入されるべきではないという点で、あなたは正しいです。これは、同じ要素を2回使用してはならないという問題の制約のためです。

したがって、アルゴリズムはより多くのこのような何かを行くだろう！：

class Solution { 
    public: 
    vector<int> twoSum(vector<int>& nums, int target) { 
     // Create a mapping from num -> index of num 
     unordered_map<int, int> m; 

     for(int i = 0; i < nums.size(); i++) { 
     // Check if we have seen our buddy 
     int buddy = target - nums[i]; 
     auto buddyIt = m.find(buddy); 

     if(buddyIt != m.end()) { 
      // Buddy found, return answer 
      return vector<int>{ buddyIt->second, i }; 
     } 

     // Buddy not found, insert current num into buddy map 
     m[nums[i]] = i; 
     } 
    } 
};