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),不过试了一下,这种解法也能过,代码就不上了。我们来分析能否降低算法复杂度,将其降到O(n)级别,我们如果想一次扫描就能得到正确结果的话,自然需要一个数据结构来记录之前扫描过的数据,然后判断这两个值的和是否为target,这里我们自然而然的可以想到用Map数据结构来存储已经遍历过的值和它的位置,PS:HashMap的查询效率是O(1)而不是O(n),如果对于这个不了解的话可以去看一下hashMap的底层实现,当我们遍历到当前值nums[i]的时候,来查询map是否还有target-nums[i]这个键,如果有的话,则找出对应的值,否则我们将当前的nums[i]作为键,位置i作为值放进数组返回。代码如下:
public static int[] twoSum(int[] nums, int target) {
int[] result = new int[2];
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(target - nums[i])) {
result[0]=map.get(target-nums[i]);
result[1]=i;
} else {
map.put(nums[i], i);
}
}
return result;
}