Tips:所有代碼實(shí)現(xiàn)包含三種語(yǔ)言（java、c++、python3）
題目
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, and you may not use the same element twice.
給定數(shù)組，返回?cái)?shù)組中相加等于給定數(shù)的兩個(gè)數(shù)的位置。
可假設(shè)僅有一個(gè)解，注意數(shù)組中的每個(gè)數(shù)僅可使用一次。
樣例
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
解題
首先看到：
輸入：一個(gè)數(shù)組（nums）和一個(gè)數(shù)（target）；
輸出：由數(shù)組（nums）的兩個(gè)索引組成的新數(shù)組，其中這兩個(gè)索引對(duì)應(yīng)的數(shù)滿(mǎn)足相加等于數(shù)（target）；
?
優(yōu)秀的程序猿很快理解了問(wèn)題，然后迅速的把問(wèn)題轉(zhuǎn)化成計(jì)算機(jī)好理解的問(wèn)題：
對(duì)于數(shù)組（nums）中每個(gè)數(shù)（temp），求數(shù)組中是否存在數(shù)x（x滿(mǎn)足x = target - temp)；
不假思索，優(yōu)秀的程序猿瞬間想到了暴力遍歷法：
對(duì)數(shù)組每個(gè)數(shù)，遍歷查找數(shù)組中此數(shù)之后的數(shù)是否存在此數(shù)的補(bǔ)集。
注意：當(dāng)我們找到一個(gè)解之后就可以立即返回了，因?yàn)轭}目中提到了可假設(shè)僅有一個(gè)解。
// java
/*
Runtime: 20 ms, faster than 41.25% of Java online submissions for Two Sum.
Memory Usage: 38.5 MB, less than 44.37% of Java online submissions for Two Sum.
*/
public int[] twoSum(int[] nums, int target){
int length = nums.length;
for (int i = 0; i < length - 1; i++){
for (int j = i + 1; j < length; j++){
if (nums[i] + nums[j] == target){
return new int[]{i, j};
}
}
}
return null;
}
// c++
/*
Runtime: 136 ms, faster than 36.44% of C++ online submissions for Two Sum.
Memory Usage: 9.5 MB, less than 79.36% of C++ online submissions for Two Sum.
*/
vector<int> twoSum(vector<int>& nums, int target) {
for(int i = 0; i < nums.size()-1; i++)
{
for(int j = i+1; j < nums.size(); j++)
{
if(nums[i] + nums[j] == target){
return {i, j};
}
}
}
return {};
}
# python3
# Runtime: 5528 ms, faster than 11.87% of Python3 online submissions for Two Sum.
# Memory Usage: 13.5 MB, less than 49.67% of Python3 online submissions for Two Sum.
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums)-1):
for j in range(i+1, len(nums)):
if nums[i] + nums[j] == target:
return [i,j]
return None
不幸的是，可以看到，這個(gè)方法的表現(xiàn)比較差，僅 Runtime 來(lái)說(shuō)，處理中下游，優(yōu)秀的程序猿當(dāng)然不僅滿(mǎn)足于此；
優(yōu)秀的程序猿繼續(xù)思考著優(yōu)化方案，再看一遍問(wèn)題：
對(duì)于數(shù)組（nums）中每個(gè)數(shù)（temp），求數(shù)組中是否存在數(shù)x（x滿(mǎn)足x = target - temp)；
優(yōu)秀的程序猿此時(shí)敏感得發(fā)現(xiàn)這其中包含一個(gè)非有序查找問(wèn)題，對(duì)于非有序查找問(wèn)題的立馬聯(lián)想到了map；
想到這里，第二個(gè)解決方案就出爐了：
- 將數(shù)組轉(zhuǎn)化成一個(gè)map，其中鍵為數(shù)組中的數(shù)，值為該數(shù)對(duì)應(yīng)得索引值；
- 對(duì)于數(shù)組（nums）中每個(gè)數(shù)（temp），查找map中是否存在等于（target-temp）的鍵，如果存在，返回該鍵對(duì)應(yīng)的值以及當(dāng)前數(shù)的索引值；
注意：如果當(dāng)前數(shù)等于target的一半，那么當(dāng)前數(shù)的補(bǔ)集就是其本身，因?yàn)轭}目要求數(shù)組中的每個(gè)數(shù)僅可使用一次，此時(shí)需判斷當(dāng)前數(shù)的補(bǔ)集不是其本身。
// java
/*
Runtime: 3 ms, faster than 99.77% of Java online submissions for Two Sum.
Memory Usage: 39.9 MB, less than 5.16% of Java online submissions for Two Sum.
*/
public int[] twoSum(int[] nums, int target){
int length = nums.length;
Map<Integer, Integer> numsMap = new HashMap<>();
for (int i = 0; i < length; i++){
numsMap.put(nums[i], i);
}
for (int i = 0; i< length; i++){
int complement = target - nums[i];
if (numsMap.containsKey(complement) && numsMap.get(complement) != i){
return new int[]{i, numsMap.get(complement)};
}
}
return null;
}
// c++
/*
Runtime: 12 ms, faster than 97.81% of C++ online submissions for Two Sum.
Memory Usage: 10.6 MB, less than 12.73% of C++ online submissions for Two Sum.
*/
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> numsMap;
for(int i = 0; i < nums.size(); i++)
{
numsMap[nums[i]] = i;
}
for(int i = 0; i < nums.size(); i++)
{
if(numsMap.count(target-nums[i]) && numsMap[target-nums[i]] != i){
return {numsMap[target-nums[i]], i};
}
}
return {};
}
# python3
# Runtime: 40 ms, faster than 73.58% of Python3 online submissions for Two Sum.
# Memory Usage: 15.2 MB, less than 5.08% of Python3 online submissions for Two Sum.
def twoSum(self, nums: List[int], target: int) -> List[int]:
nums_dict = {}
for i, num in enumerate(nums):
nums_dict[num] = i
for i, num in enumerate(nums):
if (target-num) in nums_dict and i != nums_dict[target-num]:
return [i, nums_dict[target-num]]
return None
不愧是一個(gè)優(yōu)秀的程序猿，這個(gè)Runtime表現(xiàn)讓我們很是欣慰（Memory Usage 很大是因?yàn)槲覀兪褂昧祟~外的map 存儲(chǔ)數(shù)據(jù)），忍不住的想要多看幾遍這優(yōu)美的代碼；
突然，優(yōu)秀的程序猿發(fā)現(xiàn)了在上面的解法中存在兩個(gè)問(wèn)題，
- 在查找每個(gè)數(shù)的補(bǔ)集是否存在的時(shí)候面向的是整個(gè)map，雖然對(duì)于 hashmap 來(lái)說(shuō)這不太影響性能，但是也多了一項(xiàng)判斷補(bǔ)集不是其本身啊?。。?/li>
- 算法中先實(shí)現(xiàn)了將數(shù)據(jù)填充至map，然后再逐一查詢(xún)，那么時(shí)間復(fù)雜度是O(2n)，雖然O(n)和O(2n)是基本一樣的，但是能不能再優(yōu)化一下呢？可以做到邊填充邊搜索嗎？？？
優(yōu)秀的程序猿不容許這樣的瑕疵存在，經(jīng)過(guò)短暫的思考，又一個(gè)思路浮現(xiàn)了出來(lái)：
- 創(chuàng)建一個(gè)空 map；
- 對(duì)于數(shù)組（nums）中每個(gè)數(shù)（temp），查找map中是否存在等于（target-temp）的鍵，如果存在，返回該鍵對(duì)應(yīng)的值以及當(dāng)前數(shù)的索引值；如果不存在，將該數(shù)作為鍵，其索引作為值，放入map中；
在這個(gè)思路中，相當(dāng)于對(duì)于數(shù)組中的每個(gè)數(shù)，其補(bǔ)集的搜索范圍是數(shù)組中位于此數(shù)之前的數(shù)，即做到了邊填充邊搜索，又避免了搜索范圍的浪費(fèi)。
// java
/*
Runtime: 3 ms, faster than 99.77% of Java online submissions for Two Sum.
Memory Usage: 38.7 MB, less than 36.97% of Java online submissions for Two Sum.
*/
public int[] twoSum(int[] nums, int target){
int length = nums.length;
Map<Integer, Integer> numsMap = new HashMap<>();
for (int i = 0; i < length; i++) {
int complement = target - nums[i];
if (numsMap.containsKey(complement)){
return new int[]{i, numsMap.get(complement)};
}
numsMap.put(nums[i], i);
}
return null;
}
// c++
/*
Runtime: 12 ms, faster than 97.81% of C++ online submissions for Two Sum.
Memory Usage: 10.5 MB, less than 21.80% of C++ online submissions for Two Sum.
*/
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> numsMap;
for(int i = 0; i < nums.size(); i++)
{
if(numsMap.count(target-nums[i])){
return {numsMap[target-nums[i]], i};
}
numsMap[nums[i]] = i;
}
return {};
}
# python3
# Runtime: 40 ms, faster than 73.58% of Python3 online submissions for Two Sum.
# Memory Usage: 14.4 MB, less than 5.08% of Python3 online submissions for Two Sum.
def twoSum(self, nums: List[int], target: int) -> List[int]:
nums_dict = {}
for i, num in enumerate(nums):
if (target-num) in nums_dict:
return [nums_dict[target-num], i]
nums_dict[num] = i
return None
優(yōu)秀的程序猿又嚴(yán)謹(jǐn)?shù)脤徱暳藥妆榇a，滿(mǎn)意得合上了電腦。。。
