1. 两数之和
题目
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例
给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]
我的方案
利用两层循环，暴力查找。
Java源码
class Solution {
public int[] twoSum(int[] nums, int target) {
if(nums == null || nums.length<2) return null;
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 new int[]{};
}
}
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
Dart源码
class Solution {
List<int> twoSum(List<int> nums, int target) {
if (nums == null || nums.length < 2) return [];
for (int i = 0; i < nums.length; i++) {
for (var j = i + 1; i < nums.length; i++) {
if(target == nums[i] + nums[j]){
return [i,j];
}
}
}
return [];
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
复杂度分析
- 时间复杂度：O(n²)
两层循环
- 空间复杂度: O(1)
官方方案
利用 HashMap 作为存储，键为目标值减去当前元素值，索引为值，比如
i = 0时，此时首先要判断nums[0] = 2是否在 map 中，如果不存在，那么插入键值对key = 9 - 2 = 7, value = 0，之后当i = 1时，此时判断nums[1] = 7已存在于 map 中，那么取出该value = 0作为第一个返回值，当前i作为第二个返回值，具体代码如下所示。
Java源码
class Solution {
public int[] twoSum(int[] nums, int target) {
if(nums == null || nums.length<2) return new int[]{};
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[]{};
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Dart源码
List<int> twoSum(List<int> nums, int target) {
if (nums == null || nums.length < 2) return [];
Map<int, int> map = {};
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
return [map[complement], i];
}
map[nums[i]] = i;
}
return [];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
复杂度分析
- 时间复杂度：O(n)
我们只遍历了包含有 n 个元素的列表一次。哈希表将查找时间缩短到 O(1)O(1)，所以时间复杂度为O(n)。
- 空间复杂度：O(n)
所需的额外空间取决于哈希表中存储的元素数量，该表最多需要存储 n 个元素。