题干:
难度:Easy
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]. |
解析:
由于已经确定了结果是确定的且必然只有一个,我们很容易便可以想到使用双层循环来解决问题,足够暴力也足够可行。当然,在这一题上使用这一时间复杂度为O(n^2)的算法的效率是可想而知的。很自然地,我们会想到利用HashMap来解决这一问题,因为HashMap的查找效率是常数级的。思路是建立数组元素与索引的映射(Hash),遍历数组,针对某一元素n,若在hash表的keys中有target-n存在,则可得到答案,否则以数组元素与索引值为key-value插入hash表,并继续遍历。
Java解法
class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer,Integer> h=new HashMap<Integer,Integer>();
int[] res=new int [2];
for(int i=0;i<nums.length;i++){
//查找hash表中是否有符合条件的结果,如果没有,将当前的数组元素和索引作为兼职对加入hash表中
if (h.containsKey(target-nums[i])){
res[0]=i;
res[1]=h.get(target-nums[i]);
break;
}
h.put(nums[i],i);
}
return res;
}
}
Python解法
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
h={}
res=[]
for i in range(len(nums)):
if target-nums[i] in h.keys():
res.append(i)
res.append(h[target-nums[i]])
break
h[nums[i]]=i
return res