文章目录
算法练习
面试经常会遇到算法题目，今天开启算法专栏，常用算法解析
题目
**
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个
整数，并返回它们的数组下标。 你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
**
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]
思路
- 遍历数组中的每个元素。 对于每个元素，计算它与目标值的差值。 在数组中查找是否存在这个差值。 如果找到了，返回这两个元素的索引。
- 使用哈希表：通过使用哈希表来存储已经遍历过的数字及其索引，我们可以在 O(1) 的时间内查找某个数字是否存在，从而将时间复杂度从 O(n^2) 降低到 O(n)。
减少不必要的循环：在找到第一个符合条件的数字对后，立即返回结果，避免了多余的循环。
更好的错误处理：在返回结果时，检查结果数组的长度，确保它包含两个索引，提高了代码的健壮性。
参考答案
算法1
遍历for循环比较 nums[j] == target - nums[i]
/**
*
* @param nums
* @param target
* @return
*/
public static 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};
}
}
}
return new int[]{}; // 没有找到符合条件的元素
}
思考一下有更好的解法吗？
当前时间复杂度为 O(N^2)
算法2
可以通过hash存入Key=value，value=索引的方式存储比较
关键代码
int complement = target - nums[i];
if (map.containsKey(complement)) {
return new int[]{(int) map.get(complement), i};
}
/**
* 在整数数组中找到两个数，它们的和等于给定的目标值
* 算法优化 O（n） 复杂度
*
* @param nums 整数数组
* @param target 目标值
* @return 包含两个数索引的整数数组，如果没有找到则返回空数组
*/
public static int[] optimizedTwoSum(int[] nums, int target) {
HashMap<Object, Object> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
return new int[]{(int) map.get(complement), i};
} else {
map.put(nums[i], i);
}
}
return new int[]{}; // 没有找到符合条件的元素
}
算法3
上面写完，还有一些细节需要补充
- 异常处理
- map的初始值，内存优化
- 首次不用遍历
/**
* 内存优化
* @param nums
* @param target
* @return
*/
public static int[] optimizedTwoSum2(int[] nums, int target) {
int length = nums.length;
// 初始化哈希表
Map<Integer, Integer> map = new HashMap<>(length-1);
map.put(nums[0], 0);
for (int i = 1; i < length; i++) {
int c = target - nums[i];
if (map.containsKey(c)) {
return new int[]{(int) map.get(c), i};
} else {
map.put(nums[i], i);
}
}
throw new IllegalArgumentException("No two sum solution");
}
执行结果
