今天要讨论的是「两数之和」问题,并将从哈希表解法到排序数组与双指针法、再到一遍哈希表解法的不同解决方案进行详细探讨
?
第一,使用了一种简单而有效的方法——哈希表。我们创建了一个 HashMap,用于存储已遍历过的元素及其索引。通过遍历数组,我们计算目标值与当前元素的差值,并检查哈希表中是否存在这个差值。如果存在,则返回这两个数的索引。这个方法时间复杂度为 O(n),空间复杂度为 O(n)。
?
// 哈希表解法
import java.util.HashMap;
public class TwoSum {
public int[] twoSum(int[] nums, int target) {
// 创建一个 HashMap 用于存储已经遍历过的元素及其索引
HashMap<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");
}
}
第二,利用了排序数组和双指针法。首先对数组进行排序,然后使用左右指针来查找两个数的和是否等于目标值。排序后的数组为双指针法提供了更多信息,使得查找过程更高效。这个方法时间复杂度为 O(nlogn),但是空间复杂度仅为 O(1),因为排序操作是原地进行的。
?
// 排序数组与双指针法
import java.util.Arrays;
public class TwoSum {
public int[] twoSum(int[] nums, int target) {
// 对数组进行排序,创建排序后的数组副本
int[] sortedNums = Arrays.copyOf(nums, nums.length);
Arrays.sort(sortedNums);
// 初始化左右指针
int left = 0, right = nums.length - 1;
// 使用双指针查找两数之和等于目标值
while (left < right) {
int sum = sortedNums[left] + sortedNums[right];
if (sum == target) {
int index1 = -1, index2 = -1;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == sortedNums[left] && index1 == -1) {
index1 = i;
} else if (nums[i] == sortedNums[right] && index2 == -1) {
index2 = i;
}
}
return new int[]{Math.min(index1, index2), Math.max(index1, index2)};
} else if (sum < target) {
left++;
} else {
right--;
}
}
// 如果没有找到符合条件的两个数,抛出异常
throw new IllegalArgumentException("No two sum solution");
}
}
最后,我们探讨了更高效的算法,利用了哈希表实现一遍扫描完成。这种方法只需要一次遍历,使用哈希表来存储已遍历过的数字及其索引,因此可以在更短的时间内解决问题。时间复杂度为 O(n),空间复杂度也为 O(n)。
?
// 一遍哈希表解法
import java.util.HashMap;
public class TwoSum {
public int[] twoSum(int[] nums, int target) {
// 创建一个 HashMap 用于存储已经遍历过的元素及其索引
HashMap<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");
}
}
这些方法各有优劣,但都是帮助我们更好理解和运用算法的绝佳实践!希望这份分享能够帮助到你。
?
?