题目
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.
示例
给定 nums = [2, 7, 11, 15], target = 9
nums[0] + nums[1] = 2 + 7 = 9
返回 [0, 1]
解题
在给定的数组里面，找出两个元素的下标，这两个元素要求和等于指定的一个目标和。
解法一
暴力破解很简单，遍历两遍列表，找到对应的元素x，和 target - x 即可。
public int[] twoSum(int[] nums, int target) {
for (int i = 0;i < nums.length;i++) {
for (int j = i;j < nums.length;j++) {
if (nums[i] + nums[j] == target) {
return new int[] {i, j};
}
}
}
throw new IllegalArgumentException("No such value pair.");
}
暴力破解验证.PNG
解法二
题目要求在找到数字的同时能返回数字所处的索引，那么用一个HashMap将对应的位置信息保存下来即可。
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> numPosition = new HashMap<>();
for (int index = 0;index < nums.length;index++) {
int temp = target - nums[index];
if (numPosition.containsKey(temp)) {
return new int[] {index, numPosition.get(temp)};
}
numPosition.put(nums[index], index);
}
throw new IllegalArgumentException("No two sum solution");
}
该解法是在遍历数组时，寻找target - x的值是否在HashMap中，如果未在HashMap中，则现将当前值存入，否则继续遍历。
拿题目nums = [2, 7, 11, 15], target = 9为例，当遍历到2时，target - x 为 7，7不在HashMap中，将2存入HashMap，接着遍历至7，target - 7 = 2， 此时，2 在HashMap中，完成搜索，直接返回即可。
HashMap验证.PNG
