c++ - LeetCode:TwoSum解决方案

我正在尝试使用地图来制定此答案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

最佳答案

您是正确的，因为映射应该是从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;
      }
    }
};

关于c++ - LeetCode:TwoSum解决方案，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/42850924/