leetcode经典算法之两数之和。
两数之和
给定一个int数组nums，给定一个指定值target，在数组中找到2个数的下标，它们之和等于指定值target，数组nums的数据不能重复使用，并且指定值target在数组中任意数据之和只有一种组合。
1
2
3
4
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1]
首先分析该题：
数组中元素不会重复； 不能重复使用相同元素； 有这两个做前提下这题变得比较简单起来，这里用两种方案来实现。
方法一
使用“选择相加法”，这也是最容易想到的办法，选择某一个元素，然后与其他元素分别相加，如果结果等于target，则返回这两个数的角标。
1
2
3
4
5
6
7
8
9
10
private int[] twoSum(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] == target) {
return new int[]{i, j};
}
}
}
return null;
}
方法二
利用一个Map存储nums的信息，key为nums里面的元素，value为其对应的角标。再使用一个变量diff去记住target跟当前元素的差值，最后去Map里查找这个差值，如果能找到，则返回。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
private int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> record = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
record.put(nums[i], i);
}
int diff;
for (int i = 0; i < nums.length; i++) {
diff = target - nums[i];
if (record.containsKey(diff) && record.get(diff) != i) {
return new int[]{i, record.get(diff)};
}
}
return null;
}
