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,7,11,15]给定9，那么就是下标0,1的两个元素。我们可以使用2层循环来暴力求解，但是这样复杂度就是O(n^2)，所以我们使用map来解决这个问题，一般的map存放key-value,这次我们反过来，放value-key,这样可以通过map.containsKey(target-nums[i])来判断这个元素能否和已经在map中的元素组成target
public class Solution {
public int[] twoSum(int[] nums, int target) {
int[] res=new int[2];
HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
for(int temp=0;temp<nums.length;temp++) {
if(map.containsKey(target-nums[temp])) {
res[0]=map.get(target-nums[temp]);
res[1]=temp;
break;
}
map.put(nums[temp], temp);
}
return res;
}
}
python中直接使用字典来完成
class Solution(object):
def twoSum(self, nums, target):
map = {}
for i in range(len(nums)):
if target - nums[i] in map:
return [map[target - nums[i]], i]
map[nums[i]] = i
