LeetCode1 两数之和｜哈希表做题复盘，踩坑记录

题目描述

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。

我的做题思考全过程

拿到题目，第一反应：双层循环暴力求解。
用 i 遍历第一个数，j 从 i+1 开始遍历第二个数，判断两数相加等于 target，直接返回下标。暴力写出来能跑，但是一想，如果数组很大，两层循环时间复杂度很高，会超时。

然后想到用 HashMap 做优化。
思路：遍历的时候，把已经走过的数字存到 map 里，key 存数组的值，value 存下标。
每拿到当前元素，我需要找：target - nums[i]，也就是还缺的那个数字。

• 如果 map 里面已经存在这个需要的数字，说明前面遍历过，直接返回map.get(差值)和当前 i。
• 如果找不到，就把当前数字和下标 put 放进 map，继续往后遍历。

我做题过程中踩的坑

1. put 的顺序不能写反
   一开始差点先 put 再判断 containsKey。这样遇到[3,3] target=6，会把同一个元素拿来相加，得到错误答案。必须先判断，后 put。
2. 对 return 理解模糊
   之前一直不清楚 return 之后代码怎么走，调试才明白：只要执行 return，整个方法直接结束，后面所有代码不会执行。
   if 内部 return 找到答案，循环剩余部分、函数末尾代码全部不运行。
3. 末尾必须写return new int[0];
   题目说一定有解，这行代码实际跑不到。但是 Java 语法要求：所有分支必须有返回值，不写直接编译报错。
4. HashMap 方法容易混淆

• containsKey() 判断 key 存不存在，不要直接 get 之后操作，key 不存在 get 返回 null，调用方法就空指针。
• get(key) 根据 key 拿 value，key 不存在返回 null。
• put(key,value)存入键值，相同 key 会覆盖旧值。

暴力解法代码

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[0];
    }
}

• 时间复杂度：(O(n^2))
• 空间复杂度：(O(1))

哈希表最优 AC 代码

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

• 时间复杂度：(O(n))
• 空间复杂度：(O(n))

总结

1. return 会直接终止整个方法，不是仅仅跳出循环。
2. 使用 HashMap，先判断 containsKey，再 get 取值，防止空指针。
3. 哈希表适合「找是否存在另一个数」这类题目，把已经遍历过的数据存起来，避免二次循环。