11. 给定一个整数数组和一个目标值，找出数组中和为目标值的两个数
大约 3 分钟
要在一个整数数组中找出和为目标值的两个数，可以使用以下几种方法。最常见的解法包括暴力枚举、哈希表存储法等。下面分别介绍这些方法，并提供 Java 代码示例。
一、暴力枚举法
1. 思路
暴力枚举法的思路是使用两个嵌套的循环，枚举数组中的每一个可能的数对，检查它们的和是否等于目标值。如果找到和为目标值的两个数，则返回它们的索引。
2. 代码实现
public class TwoSumBruteForce {
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[i] + nums[j] == target) {
return new int[]{i, j}; // 找到符合条件的两个数的索引
}
}
}
throw new IllegalArgumentException("No two sum solution");
}
public static void main(String[] args) {
int[] nums = {2, 7, 11, 15};
int target = 9;
int[] result = twoSum(nums, target);
System.out.println("Indexes: " + result[0] + ", " + result[1]);
}
}3. 时间复杂度
- 时间复杂度：
O(n^2)，其中n是数组的长度。每对数字都要进行比较，因此时间复杂度较高。 - 空间复杂度：
O(1)，仅使用了常数级别的额外空间。
二、哈希表存储法
1. 思路
使用哈希表可以将时间复杂度降为 O(n)。具体步骤是遍历数组，将每个元素和其索引存入哈希表，并检查目标值减去当前元素的差值是否已经在哈希表中。如果存在，则说明找到了两个数，它们的和等于目标值。
2. 代码实现
import java.util.HashMap;
import java.util.Map;
public class TwoSumHashMap {
public static 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(nums[i], i); // 将当前数字和它的索引放入哈希表
}
throw new IllegalArgumentException("No two sum solution");
}
public static void main(String[] args) {
int[] nums = {2, 7, 11, 15};
int target = 9;
int[] result = twoSum(nums, target);
System.out.println("Indexes: " + result[0] + ", " + result[1]);
}
}3. 时间复杂度
- 时间复杂度：
O(n)，其中n是数组的长度。每个元素只需被访问一次。 - 空间复杂度：
O(n)，哈希表存储了数组中的每个元素。
三、双指针法（适用于有序数组）
1. 思路
如果数组是有序的，可以使用双指针法。将两个指针分别放在数组的头部和尾部，逐渐向中间移动，直到找到和为目标值的两个数。
2. 代码实现
import java.util.Arrays;
public class TwoSumTwoPointers {
public static int[] twoSum(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) {
return new int[]{left, right}; // 找到符合条件的两个数的索引
} else if (sum < target) {
left++;
} else {
right--;
}
}
throw new IllegalArgumentException("No two sum solution");
}
public static void main(String[] args) {
int[] nums = {2, 7, 11, 15};
int target = 9;
int[] result = twoSum(nums, target);
System.out.println("Indexes: " + result[0] + ", " + result[1]);
}
}3. 时间复杂度
- 时间复杂度：
O(n)，其中n是数组的长度。 - 空间复杂度：
O(1)，只使用了常数级别的额外空间。
四、总结
- 暴力枚举法：简单直观，但时间复杂度高，适用于小规模数据。
- 哈希表存储法：效率高，适用于任意顺序的数组，时间复杂度为
O(n)。 - 双指针法：适用于已排序的数组，时间复杂度为
O(n)，且空间复杂度为O(1)。
在实际开发中，哈希表存储法通常是最常用的解决方案，因其时间复杂度较低且适用于无序数组。双指针法则在处理有序数组时更为高效。