本文給出了：TwoSum解決方案

我試圖使用地圖，以使算法此答案https://leetcode.com/problems/two-sum/#/description爲O（n），但出於某種原因，我發現了不當的指標進行了大量的測試情況下，我很試圖本文給出了：TwoSum解決方案

從我可以告訴，我做正確的檢查的迭代器，但這些都是一種新的給我，我不能完全肯定，如果我回來，我想正確的指標。

//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

來源

2017-03-17 Keaton MacLeod

更改這個'它= myMap.begin（）'本'它= myMap.end（）'...其實從頭開始。你有一堆發現我迷路了，不能遵循你的邏輯。 – Arash

如果循環結束會發生什麼？那你什麼時候回來？ –

哇哦，我不知道myMap.begin（）是怎麼在那裏，但它是最絕的要myMap.end（） –

你是在地圖上應該從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; 
     } 
    } 
};

來源

2017-10-15 10:51:12 Bill

本文給出了：TwoSum解決方案

回答

相關問題