怎样查看别人网站流量,效果图外包,如何免费申请自己的网站,网络推广怎么入门今天要讨论的是「两数之和」问题#xff0c;并将从哈希表解法到排序数组与双指针法、再到一遍哈希表解法的不同解决方案进行详细探讨 哈希表解法#xff1a;
第一#xff0c;使用了一种简单而有效的方法——哈希表。我们创建了一个 HashMap#xff0c;用于存储已遍历过的元…今天要讨论的是「两数之和」问题并将从哈希表解法到排序数组与双指针法、再到一遍哈希表解法的不同解决方案进行详细探讨 哈希表解法
第一使用了一种简单而有效的方法——哈希表。我们创建了一个 HashMap用于存储已遍历过的元素及其索引。通过遍历数组我们计算目标值与当前元素的差值并检查哈希表中是否存在这个差值。如果存在则返回这两个数的索引。这个方法时间复杂度为 O(n)空间复杂度为 O(n)。 // 哈希表解法
import java.util.HashMap;public class TwoSum {public int[] twoSum(int[] nums, int target) {// 创建一个 HashMap 用于存储已经遍历过的元素及其索引HashMapInteger, 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 用于存储已经遍历过的元素及其索引HashMapInteger, 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);}
}
这些方法各有优劣但都是帮助我们更好理解和运用算法的绝佳实践希望这份分享能够帮助到你。
