如何判断数组中是否存在和为指定值的两个数
这是一道面试题，简称为“两数之和”，即给定一个值 n 和一个数组 nums，判断数组 nums 中是否存在两个数，其和值为 n。本篇经验将分享两种算法，其时间复杂度分别为 O(n^2) 和 O(n)。注意：数组可以包含重复元素，但每个元素只允许使用一次。
算法一：双重遍历
实现基于双重遍历的普通算法，算法思想为：通过双重循环，遍历数组中每一组两数组和，如果和值为指定值，则返回 true，否则返回 false。
```
public boolean twoSum(int[] nums, int target) {
for (int i 0; i < nums.length; i ) {
for (int j i 1; j < nums.length; j ) {
if (nums[i] nums[j] target) {
return true;
}
}
}
return false;
}
```
算法二：使用 Map
实现基于 Map 的改进算法，算法思想为：第一次遍历数组，将数组所有元素添加到 Map 中，再次遍历数组，对于数组的每一个值 k，判断 Map 中是否存在 n-k（n即指定和值），如果存在，则返回 true，否则返回 false。
```
public boolean twoSum(int[] nums, int target) {
Map
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 ((complement) (complement) ! i) {
return true;
}
}
return false;
}
```
编写本地测试主方法
在主方法中调用两种算法来测试其准确性。
```
public static void main(String[] args) {
int[] nums {2, 7, 11, 15};
int target 9;
Solution solution new Solution();
((nums, target));
}
```
运行本地测试主方法
运行本地测试主方法，观察控制台输出，符合预期，两个算法本地测试均通过。
算法复杂度分析
数组长度为 n，算法一：需要双重遍历，时间复杂度为 O(n^2)，空间复杂度为 O(1)。算法二：只需一次遍历辅助查找时间复杂度为 O(1) 的 Map，总体时间复杂度为 O(n)，空间复杂度为 O(n)。
版权声明：本文内容由互联网用户自发贡献，本站不承担相关法律责任.如有侵权/违法内容,本站将立刻删除。
