Problem: 1. 两数之和

整体思路

这段代码旨在高效地解决 “两数之和” 问题。与 O(N^2) 的暴力枚举法相比，此版本采用了一种经典的 “空间换时间” 策略，利用 哈希表 (HashMap) 将时间复杂度优化到了线性级别 O(N)。

该算法的核心思想是，在遍历数组的同时，利用哈希表快速查找每个数字所需的“另一半”。

算法的逻辑步骤可以分解如下：

1. 数据结构选择：

   • 算法选择 HashMap 作为核心数据结构。这个哈希表将用于存储已经遍历过的数字及其对应的索引，即 (数字 -> 索引) 的键值对。
   • 目的：哈希表提供了平均时间复杂度为 O(1) 的查找操作。这使得我们能够即时地回答“我们之前是否见过某个数字？”这个问题。

2. 单次遍历与查找：

   • 算法只需对 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 存入哈希表中，以供后续的迭代查找。

3. 返回结果：

   • 由于题目保证有且仅有一个解，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: 该数字对应的索引
        Map<Integer, 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)

1. 循环：算法的核心是一个 for 循环，它严格地遍历 nums 数组一次。如果数组的长度为 N，这个循环将执行 N 次。
2. 循环内部操作：
   • 在循环的每一次迭代中，执行的主要操作是 map.containsKey() 和 map.put()。
   • 对于 HashMap，这两个操作的平均时间复杂度都是 O(1)。
   • 其余的算术和赋值操作也是 O(1)。

综合分析：
算法由 N 次 O(1) 的操作组成。因此，总的时间复杂度是 N * O(1) = O(N)。

空间复杂度：O(N)

1. 主要存储开销：算法使用了一个哈希表 map 来存储已经遍历过的数字和它们的索引。
2. 空间大小：在最坏的情况下（例如，解在数组的最后两个元素，或者无解），哈希表需要存储 N-1 或 N 个键值对。因此，哈希表占用的空间与输入数组 nums 的大小 N 成线性关系。

综合分析：
算法所需的额外空间主要由哈希表 map 决定。因此，其空间复杂度为 O(N)。