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].
题意简单明了。就是返回求和的两个数的索引。假设输入有唯一解。
实现：
public int[] twoSum(int[] nums, int target) {
int[] res = new int[2];
for (int i = 0; i < nums.length; i++) {
int a = nums[i];
for (int j = 0; j < nums.length; j++) {
if (j != i) {
int b = nums[j];
if (a + b == target) {
res[0] = i;
res[1] = j;
}
}
}
}
return res;
}
。。。提交后发现
Runtime: 74 ms, faster than 5.14% of Java online submissions for Two Sum.
Memory Usage: 38.6 MB, less than 38.09% of Java online submissions for Two Sum.
发现和提交者对比后这个算法的性能低到不行。大约O（n^2）果然最容易想到的往往都是最坑的。
后面查看大神们的思路后的HashMap实现：
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
return new int[] {map.get(complement), i};
}
map.put(nums[i], i);
}
return new int[2];
}
看来还是得多思考，最后结果：
Runtime: 3 ms, faster than 99.36% of Java online submissions for Two Sum.
Memory Usage: 39.2 MB, less than 22.78% of Java online submissions for Two Sum.
