vvrf / DSA.log

问题拆解

给定一个整数数组 nums 和目标值 target，需要找到两个不同位置的数，让它们之和等于目标值。

暴力做法会枚举所有数对，时间复杂度是 O(n²)。真正值得抓住的问题是：当遍历到 x 时，我们只需要知道 target - x 是否已经出现过。

把“寻找另一个数”换成“查询另一个数”，哈希表正好适合做这件事。

一次遍历

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> seen = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int need = target - nums[i];
        if (seen.containsKey(need)) {
            return new int[]{seen.get(need), i};
        }
        seen.put(nums[i], i);
    }
    return new int[0]; // 题目保证有解，走不到这里
}

def twoSum(nums: list[int], target: int) -> list[int]:
    seen = {}

    for index, value in enumerate(nums):
        need = target - value
        if need in seen:
            return [seen[need], index]
        seen[value] = index

    return []  # 题目保证有解，走不到这里

func twoSum(nums []int, target int) []int {
    seen := make(map[int]int)
    for i, v := range nums {
        if j, ok := seen[target-v]; ok {
            return []int{j, i}
        }
        seen[v] = i
    }
    return nil // 题目保证有解，走不到这里
}

pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
    let mut seen = std::collections::HashMap::new();
    for (i, &v) in nums.iter().enumerate() {
        if let Some(&j) = seen.get(&(target - v)) {
            return vec![j as i32, i as i32];
        }
        seen.insert(v, i);
    }
    vec![] // 题目保证有解，走不到这里
}

为什么先查询再写入？因为题目要求不能重复使用同一个元素。如果先放入当前数字，当 target == value * 2 时，就可能错误地匹配到自己。

复杂度

指标	复杂度	原因
时间	`O(n)`	数组只遍历一次
空间	`O(n)`	最坏情况下保存所有元素

可以迁移的模式

题目要求快速判断“某个值是否出现过”；
需要保存“值 → 位置”或“值 → 次数”的映射；
一边遍历，一边利用之前的信息完成当前决策。

下次看到“配对”“补数”“是否存在”这些词，可以先想想哈希表。