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, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,Because nums[0] + nums[1] = 2 + 7 = 9,return [0,1].
2.題意
給定一個整形數(shù)組，一個整形目標(biāo)值澄耍，找出這個數(shù)組中兩個元素的下標(biāo)鹃唯，這兩個元素之和等于目標(biāo)值洲劣。比如數(shù)組nums是[2, 7, 11, 15]姐赡，目標(biāo)值是9的話银还，那么nums[0] + nums[1]就等于9，所以返回[0, 1]
3.思路
首先需要明確數(shù)組是無序的。
其次需要知道涡尘，返回的是數(shù)組的下標(biāo)不是這兩個元素的值。所以不能使用排序后响迂，兩頭往中間找的方式考抄。
具體做法就是：
使用一個map保存元素數(shù)字與下標(biāo)之間的映射關(guān)系。我們從前往后掃描數(shù)組蔗彤，這個map只保存了從第一個元素川梅，到當(dāng)前待掃描元素的前一個元素。也就是說幕与，待掃描元素之前的元素我們已經(jīng)都保存了每個數(shù)值以及它對應(yīng)的下標(biāo)挑势。
掃描當(dāng)前元素時镇防，我們用目標(biāo)值target - nums[current]得到一個差值啦鸣，這個差值可以理解為需要與當(dāng)前元素nums[current]搭配形成target的“配偶”。我們在map中查找是夠存在這個“配偶”来氧，也就是說看看前面掃描的那堆元素里面是不是存在該元素的“配偶”诫给。
如果找到“配偶”，返回【配偶的下標(biāo)啦扬，當(dāng)前元素的下標(biāo)current】中狂，如果沒有找到，那就將當(dāng)前元素以及對應(yīng)的下標(biāo)存入到map中扑毡。
4.代碼實現(xiàn)
本系列的文章都會使用兩種語言實現(xiàn)：java和python胃榕，也是筆者最近用的較多的，不排除后面會繼續(xù)加入其它的語言瞄摊。
java代碼參見如下：
class Solution { public int[] twoSum(int[] nums, int target) { HashMap num_index = new HashMap();
for(int i = 0; i < nums.length; i++) {
if(num_index.containsKey(target - nums[i])) {
return new int[] {num_index.get(target - nums[i]), i};
}
num_index.put(nums[i], i);
}
throw new IllegalArgumentException("No solution for two sum");
}
}
python代碼參見如下：
class Solution:
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
num_index = {}
for i in range(len(nums)):
if target - nums[i] in num_index.keys():
return [num_index.get(target - nums[i]), i]
num_index[nums[i]] = i
return []
