c++ - 力扣 : TwoSum Solution

Question

我正在尝试使用 map 来制作此答案的算法 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 的索引的映射，但不应立即将其插入到映射中。这是由于问题的约束

you may not use the same element twice.

因此，算法会更像这样:

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