[hashmap|空間換時間] leetcode 1 兩數之和

1.題目

題目鏈接
給定一個整數數組 nums 和一個目標值 target，請你在該數組中找出和為目標值的那兩個整數，并返回他們的數組下標。
你可以假設每種輸入只會對應一個答案。但是，數組中同一個元素不能使用兩遍。
示例：

給定 nums = [2, 7, 11, 15], target = 9
因為 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

2.分析

2.1.第一印象

java計算hash值？第一眼的想法為“暴力求解”，即利用兩層for循環遍歷數組，判斷是否有滿足條件的數對：

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

時間復雜度為O(n²)。能否在此基礎上進行改進？

2.2.HashMap

HashMap存儲著key-value鍵值對，一個顯著的優勢是能夠將查找的時間復雜度降為O(1)。
那么本題可以這么理解：對于當前遍歷到的數a，只需要判斷target - a是否在數組中即可。
此時key就是nums數組中第i個數的值，value就是數組中第i個數的下標(也就是i)。也就是說，同樣是尋找一個數，通過構造一個反向的從值到下標的映射，可以壓縮查找的時間。
原： 使用內層for循環來判斷另一個數是否滿足要求

for(int i = 0; i < nums.size(); i++) {for(int j = i + 1; j < nums.size(); j++) {//do something...}
}

改： 使用內層if來以O(1)的時間復雜度判斷另一個數是否滿足要求

for(int i = 0; i < nums.size(); i++) {if(map.find(target - nums[i] != map.end())) {//do something...}
}

修改后的代碼便實現了所謂的空間換時間：用hashmap的 O(n) 的存儲效率換取了 O(1) 的查找效率。

3.代碼

C++中hashmap以unordered_map的形式實現。

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