设计网站建站,深圳网站建设软件开发公司排名,旅游的网站怎么做,外贸seo建站Problem: 1. 两数之和 文章目录整体思路完整代码时空复杂度时间复杂度#xff1a;O(N)空间复杂度#xff1a;O(N)整体思路
这段代码旨在高效地解决 “两数之和” 问题。与 O(N^2) 的暴力枚举法相比#xff0c;此版本采用了一种经典的 “空间换时间” 策略#xff0c;利用 … Problem: 1. 两数之和 文章目录整体思路完整代码时空复杂度时间复杂度O(N)空间复杂度O(N)整体思路
这段代码旨在高效地解决 “两数之和” 问题。与 O(N^2) 的暴力枚举法相比此版本采用了一种经典的 “空间换时间” 策略利用 哈希表 (HashMap) 将时间复杂度优化到了线性级别 O(N)。
该算法的核心思想是在遍历数组的同时利用哈希表快速查找每个数字所需的“另一半”。
算法的逻辑步骤可以分解如下 数据结构选择 算法选择 HashMap 作为核心数据结构。这个哈希表将用于存储已经遍历过的数字及其对应的索引即 (数字 - 索引) 的键值对。目的哈希表提供了平均时间复杂度为 O(1) 的查找操作。这使得我们能够即时地回答“我们之前是否见过某个数字”这个问题。 单次遍历与查找 算法只需对 nums 数组进行一次 for 循环遍历。在循环的每一步对于当前数字 nums[i]算法执行两个核心操作且顺序非常关键 a. 计算并查找“补数”首先计算出要与 nums[i] 相加才能得到 target 的那个“补数” other即 other target - nums[i]。然后算法立即在哈希表中检查是否存在这个 other。 b. 处理查找结果 如果找到了 (map.containsKey(other))这意味着 other 这个数字在数组的前面部分0 到 i-1 的索引中已经出现过。我们已经找到了解此时直接返回 other 的索引从哈希表中获取 map.get(other)和当前数字的索引 i。如果没有找到这意味着在已经遍历过的数字中没有 nums[i] 的“另一半”。那么nums[i] 本身可能就是未来某个数字的“另一半”。因此算法将当前数字 nums[i] 及其索引 i 存入哈希表中以供后续的迭代查找。 返回结果 由于题目保证有且仅有一个解if 条件一定会在某个时刻被满足并返回结果。因此理论上最后的 return null; 是不可达的但在语法上是必需的以防编译器报错。
通过这种“边遍历边记录”的方式算法将寻找配对数的过程从 O(N) 的线性扫描缩短为 O(1) 的哈希查找从而实现了整体性能的飞跃。
完整代码
import java.util.HashMap;
import java.util.Map;class Solution {/*** 在数组中找出和为目标值的两个数的索引。* param nums 整数数组* param target 目标和* return 包含两个索引的数组如果不存在则返回 null*/public int[] twoSum(int[] nums, int target) {int n nums.length;// map: 用于存储已遍历过的数字及其索引。// Key: 数组中的数字// Value: 该数字对应的索引MapInteger, Integer map new HashMap();// 单次遍历数组for (int i 0; i n; i) {// 计算当前数字 nums[i] 需要配对的“另一半”int other target - nums[i];// 关键步骤检查“另一半”是否已经存在于哈希表中// 这是 O(1) 的高效查找操作if (map.containsKey(other)) {// 如果存在说明我们找到了解。// map.get(other) 是“另一半”的索引i 是当前数字的索引。return new int[]{map.get(other), i};}// 如果“另一半”不存在则将当前数字和它的索引存入哈希表// 以便后续的元素可以查找它作为配对。map.put(nums[i], i);}// 根据题目假设总会有一个解所以理论上不会执行到这里。return null;}
}时空复杂度
时间复杂度O(N)
循环算法的核心是一个 for 循环它严格地遍历 nums 数组一次。如果数组的长度为 N这个循环将执行 N 次。循环内部操作 在循环的每一次迭代中执行的主要操作是 map.containsKey() 和 map.put()。对于 HashMap这两个操作的平均时间复杂度都是 O(1)。其余的算术和赋值操作也是 O(1)。
综合分析 算法由 N 次 O(1) 的操作组成。因此总的时间复杂度是 N * O(1) O(N)。
空间复杂度O(N)
主要存储开销算法使用了一个哈希表 map 来存储已经遍历过的数字和它们的索引。空间大小在最坏的情况下例如解在数组的最后两个元素或者无解哈希表需要存储 N-1 或 N 个键值对。因此哈希表占用的空间与输入数组 nums 的大小 N 成线性关系。
综合分析 算法所需的额外空间主要由哈希表 map 决定。因此其空间复杂度为 O(N)。
