LeetCode 补拙笔记

0. 前言

• 日期：2026.06.07
• 题目：1. 两数之和
• 难度：简单
• 标签：数组、哈希表

1. 题目理解

问题描述： 给定一个整数数组 nums 和一个整数目标值 target，请在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。

• 假设每种输入只会对应一个答案。
• 不能使用两次相同的元素。
• 可以按任意顺序返回答案。

示例：

输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9，所以返回 [0, 1]。

2. 解题思路

核心观察

• 暴力解法：双重循环枚举所有组合，时间复杂度 $O(n^2)$，效率低。
• 哈希表解法：利用哈希表的 $O(1)$ 查询特性，边遍历边记录，将复杂度降至 $O(n)$。
• 优化版：采用双指针同时从数组首尾向中间遍历，进一步优化哈希表的查询效率，减少单次循环中的判断次数。

算法步骤

1. 初始化一个哈希表，用于存储“值-索引”对。
2. 同时从数组的左右两端开始遍历。
3. 对当前元素，检查哈希表中是否存在 target - 当前元素。
4. 若存在，则直接返回两个索引；若不存在，则将当前元素存入哈希表。
5. 遍历结束即找到答案。

3. 代码实现

package lc0_lc99.lc1;

import java.util.HashMap;

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int[] res = new int[2];
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                res[0] = map.get(nums[i]);
                res[1] = i;
            }
            map.put(target - nums[i], i);
        }
        return res;
    }
}

4. 代码优化说明

class Solution {
public int[] twoSum(int[] nums, int target) {
    Map<Integer,Integer> map = new HashMap<>();
    // 双指针同时从首尾向中间遍历
    for(int i = 0, j = nums.length - 1;i <= j;i++,j--){
        // 检查左侧元素是否已有匹配项
        if(map.containsKey(target - nums[i])){
            return new int[]{i,map.get(target - nums[i])};
        }
        map.put(nums[i],i); // 存入左侧元素
        // 检查右侧元素是否已有匹配项
        if(map.containsKey(target - nums[j])){
            return new int[]{j,map.get(target - nums[j])};
        }
        map.put(nums[j],j); // 存入右侧元素
    }
    return new int[]{0,0};
}
}

5. 复杂度分析

• 时间复杂度：$O(n)$，优化版仍是线性时间复杂度，但通过双指针遍历，减少了循环次数，常数级优化。
• 空间复杂度：$O(n)$，哈希表在最坏情况下需要存储全部 $n$ 个元素。

6. 总结

• 核心：利用哈希表将查询时间降为 $O(1)$，实现线性时间复杂度。
• 优化：双指针遍历减少了循环次数，能更快地找到答案，代码也更紧凑。
• 关键技巧：边遍历边存入哈希表，而不是先存后查，避免了同一元素被重复使用的问题。