1，问题描述
原始leetcode题目网址1. 两数之和
难度：简单
提示：
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。
示例 1：
1
2
3
| 输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
|
示例 2：
1
2
| 输入：nums = [3,2,4], target = 6
输出：[1,2]
|
示例 3：
1
2
| 输入：nums = [3,3], target = 6
输出：[0,1]
|
提示：
2 <= nums.length <= 104-109 <= nums[i] <= 109-109 <= target <= 109- 只会存在一个有效答案
**进阶：**你可以想出一个时间复杂度小于 O(n2) 的算法吗？
2，初步思考
首先暴力遍历破解是可以解题的，本质就是全局去挨个相加测试结果是否等于target，但是算法时间复杂度为O(n^2)
进阶要求时间复杂度小于O(n^2)，那么一定是有排序的，因为他没有空间复杂度的要求，所以我们就直接使用空间换时间来解决
初步思考的结果是错误的，把问题想复杂了
3，代码处理
第一次的思路想复杂了
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
| import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class _1 {
static List<Integer> list = new ArrayList<>();
static Map<Integer, Integer> map = new HashMap<>();
public int[] twoSum(int[] nums, int target) {
sort(nums);
int indexA = 0;
int indexB = 0;
int nextNum = 0;
for (Integer num : list) {
nextNum = target - num;
if (num == nextNum) {
List<Integer> integers = map.get(num);
return new int[]{integers.get(0), integers.get(1)};
}
if (map.containsKey(nextNum)) {
return new int[]{map.get(nextNum).get(0), map.get(num).get(0)};
}
}
return null;
}
private int[] sort(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
int num = nums[i];
if (map.containsKey(num)) {
if (num * 2 == target) {
return new int[]{map.get(num), i};
}
} else {
map.put(num, i);
}
if (list.isEmpty()) {
list.add(num);
} else if (list.getFirst() > num) {
list.addFirst(num);
} else if (list.getLast() < num) {
list.add(num);
} else {
for (int j = 1; j < list.size() - 1; i++) {
if (list.get(j) > num) {
list.add(j, num);
break;
}
}
}
}
return null;
}
}
|
下面是我思考之后的另一个解答，时间复杂度O(n)，空间复杂度O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
| public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int num = nums[i];
int diff = target - num;
if (map.containsKey(diff)) {
return new int[]{map.get(diff), i};
} else {
map.put(num, i);
}
}
return null;
}
|
4，思考过程
其他条件是很普通的，我们看一下后面的条件你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
4.1，条件分析
1，每种输入只会对应一个答案
如果有重复的数字，那么他们只有如下几种情况
1️⃣这个重复的数字相加为target，并且他们一定只有2个
2️⃣重复数字除了上述1️⃣中的情况，其他时候不可能是结果
2，你不能使用相同的元素
每个数字只能使用一次（它的索引只有一个）
4.2，思路解析
我知道target，并且我遍历的时候，我知道当前数字num，那么我直接去找另一个匹配数字（target-num）即可
如何找呢，直接使用hashMap散列表去存储key(数字num)、value（索引index）
如果有就直接返回，没有就直接map.put存储进去就行