题目描述

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那两个整数,并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。

思路:

  1. 题目是要求nums中有两个数和是target,那么就应该是nums中会存在一个target - nums[i]的数,这种变换思维是要具备,即当题目需要得到什么结果,将这个结果推到出等价的描述,得到一些充分条件或者必要条件,在想办法(算法)去得到这些条件,当然也要具备一些基础知识,比如hash思想,知道hash方法它有哪些应用场景和它还有可能解决什么问题。
  2. 题目转换为nums中找到一个target - nums[i]的数,那么可以先得到这些target - nums[i],即得到两个nums.length大小的数组,再去找到两个数组中相同的数,找到相同的数,最容易的方法就是通过hash思想,有很多类似找相同数或者元素都有借助hash思想。

答案

java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/**
* 题目1:给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那两个整数,并返回他们的数组下标。
* 你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素
* 注:此解决方法有问题,会申请大量内存,优化方向为动态hash表即官方解法。
* e.g: 给定 nums = [2, 7, 11, 15], target = 9
* 因为 nums[0] + nums[1] = 2 + 7 = 9
* 所以返回 [0, 1]
* @param nums
* @param target
* @return
*/
private static int[] solution01(int[] nums, int target) {
int length = nums.length;
if (length <= 0) {
throw new IllegalArgumentException();
}
// 先找到nums中最小值和最大值
int min = nums[0], max = nums[0];
for (int i = 0; i < length; i++) {
if (nums[i] > max) {
max = nums[i];
}
if (nums[i] < min) {
min = nums[i];
}
}
int offset = -min, tableSize = max - min + 1;
int[] map = new int[tableSize];
for (int i = 0; i < tableSize; i++) {
map[i] = -1;
}
for (int i = 0; i < length * 2; i++) {
if (i < length) {
// 在map中记录下nums的位置信息
map[nums[i] + offset] = i;
} else {
int index = target - nums[i - length] + offset;
if (0 <= index && index < tableSize && map[index] != -1 && map[index] != i - length) {
return new int[]{i - length, map[index]};
}
}
}
throw new IllegalArgumentException();
}

/**
* 题目1 官方解答
* @param nums
* @param target
* @return
*/
private static int[] solution02(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
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);
}
throw new IllegalArgumentException("No two sum solution");

}

算法复杂度

solution01算法时间复杂度为O(n),但空间复杂度根据nums的元素决定可能会特别大,该方法不可取。
solution02算法时间leetCode上说是复杂度是O(n),但我认为应该是大于O(n),因为map.put(nums[i], i);这个操作时间复杂度可能会是log(n),所以整体复杂度应该略大于O(n)。