python哈希，《LeetBook》LeetCode題解(1) : Two Sum[E]——哈希Map的應用

001.Two Sum[E]

• • Two SumE
  • 題目
  • 思路
    • 1雙重循環
    • 2 排序
    • 3 Hashmap

1.題目

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution.

python哈希？Example:

Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

2.思路

2.1雙重循環

最簡單的思路，兩重循環，沒啥技術含量，速度很慢，畢竟是O(N2)

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {vector<int> result;for(int i = 0;i < nums.size();i++){for(int j = i+1;j < nums.size();j++)if(nums[i] + nums[j] == target){result.push_back(i);result.push_back(j);return result;}}}
};

2.2 排序

其實簡單的想，用一個排序都能把復雜度降到O(NlogN)，通過排序，然后用兩個指針從前后掃描逼近真值，因為一定會有一個值滿足，然后通過值去原數組里找對應的下標（這里其實就可以考慮，如果當初就用一個數據結構存好鍵值對應關系就好了，其實就是hashmap，下面的做法就用到了）
（下面代碼是 dugu9sword寫的java代碼，我就沒寫成c++的，主要看思路，還是比較好理解的）

public class Solution {public int[] twoSum(int[] nums, int target) {int[] nums_sorted=new int[nums.length];System.arraycopy(nums,0,nums_sorted,0,nums.length);//Quicksort.Arrays.sort(nums_sorted);//Find the two numbers. O(n)int start=0;int end=nums_sorted.length;while(start<end){while(nums_sorted[start]+nums_sorted[--end]>target);if(nums_sorted[end]+nums_sorted[start]==target)break;while(nums_sorted[++start]+nums_sorted[end]<target);if(nums_sorted[end]+nums_sorted[start]==target)break;}//find the indices of the two numbersint[] ret=new int[2];int index=0;int a=nums_sorted[start];int b=nums_sorted[end];for(int i=0;i<nums.length;i++)if(nums[i]==a || nums[i]==b)ret[index++]=i;return ret;}
}

2.3 Hashmap

初中一題多解的例題？最后一種是比較聰明的做法，用hashmap，hashmap是內部存儲方式為哈希表的map結構，哈希表可以達到查找O(1)，哈希表的介紹可以看這里, C++實現Hashmap的方式，這里用unordered_map關聯容器，可以實現鍵值對應。

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {vector<int> result;unordered_map<int,int> mymap;int res;for(int i = 0;i < nums.size();i++){res = target - nums[i];unordered_map<int,int>::iterator it = mymap.find(res);if(it != mymap.end()){return vector<int>({it->second,i});}mymap[nums[i]] = i;}}
};