Two sum
indices,index的复数形式
题目
给定一个整数数组，返回两个数字索引，使其相加等于特定值。
假定每次输入只有一个确定解，并且不能重复使用相同元素。
示例：
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
Solution
思路一：暴力求解
对每一个元素x，查找是否存在target - x.
public 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[j] == target - nums[i]) {
return new int[] { i, j};
}
}
}
throw new IllegalArgumentException("No two sum solution");
}
复杂度分析
- 时间复杂度：\(O(n^2)\).
- 空间复杂度：\(O(1)\).
思路二：两遍哈希表
为了改进时间复杂度，需要更有效的方式检测数组里补数是否存在。如果补数存在，我们需要查找它的索引。维持元素和索引之间映射最有效的方式就是哈希表。
通过用空间换取速度，将查找时间由\(O(n)\)减至\(O(1)\)。哈希表可以完成这个目的。
简单实现为两个迭代。
- 添加元素值和索引到哈希表。
- 检测元素补数是否存在
target - nums[i],注意补数不能是自己。
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
map.put(nums[i], i);
}
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement) && map.get(complement) != i) {
return new int[] { i, map.get(complement)};
}
}
throw new IllegalArgumentException("No two sum solution");
}
复杂度分析
- 时间复杂度：\(O(n)\).
- 空间复杂度：\(O(n)\).
一遍哈希表
一遍插入元素，一边往回检测哈希表中是否已经存在当前元素的补数。
public int[] twoSum(int[] nums, int target) {
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(num[i], i);
}
throw new IllegalArguementException("No two sum solution");
}
复杂度分析
- 时间复杂度：\(O(n)\).
- 空间复杂度：\(O(n)\).