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에서 매핑해야한다는 올바른지,하지만 바로지도에 삽입 할 수 없습니다. 이는 동일한 요소를 두 번 사용하지 않아도되는 문제의 제약 때문에 발생합니다.

동일한 요소를 두 번 사용할 수 없습니다.

따라서, 알고리즘은 더 이런 식으로 뭔가를 갈 것!!

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; 
     } 
    } 
};