哈希

两数之和

• 使用哈希表来存储已经遍历过的元素及其索引
• 在遍历数组时，检查哈希表中是否存在目标值与当前元素的差值
• 如果存在，则返回这两个数的索引
• 如果不存在，则将当前元素及其索引添加到哈希表中

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i]; // 计算目标值与当前元素的差值
        if (map.containsKey(complement)) { // 如果哈希表中存在目标值与当前元素的差值
            return new int[] { map.get(complement), i }; // 返回这两个数的索引
        }
        map.put(nums[i], i); // 将当前元素及其索引添加到哈希表中
    }
    return new int[] { -1, -1 };
}

三数之和

• 排序之后，a + b + c = 0 可以转为 b + c = -a；
• HashSet 用来判断是否有目标数 c = -a - b；
• 用 while 跳过 b 重复是比你原来的 j > i + 2 && ... 条件更鲁棒；

//第一层固定 a = nums[i]
//第二层遍历 b = nums[j]
//然后通过 HashSet 查找是否存在 c = -a - b

public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    Arrays.sort(nums);
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] > 0) break; // 优化：升序数组，a>0则无解 因为b和c也会大于0
        if (i > 0 && nums[i] == nums[i - 1]) continue; // a去重：如果当前元素和前一个元素相同，则跳过

        HashSet<Integer> set = new HashSet<>();
        for (int j = i + 1; j < nums.length; j++) {
            int c = -nums[i] - nums[j]; // 计算三元组元素c = -a - b
            if (set.contains(c)) {
                result.add(Arrays.asList(nums[i], nums[j], c)); // 如果c在set中，则将三元组加入结果集
                // 去重：跳过重复的 b，防止生成重复三元组。
                while (j + 1 < nums.length && nums[j] == nums[j + 1]) j++;
            }
            set.add(nums[j]); // 当前的 b = nums[j] 加到 HashSet 中，以便下一轮可以判断：是否存在 c = -a - b
        }
    }
    return result;
}

赎金信

• 使用哈希表来记录 magazine 中每个字符的出现次数
• 遍历 ransomNote 中的每个字符，如果该字符在哈希表中不存在或出现次数为0，则返回 false
• 如果该字符在哈希表中存在且出现次数大于0，则将该字符的出现次数减1
• 如果遍历完 ransomNote 中的所有字符后，哈希表中所有字符的出现次数都为0，则返回 true

public boolean canConstruct(String ransomNote, String magazine) {
    if(ransomNote.length() > magazine.length()) return false; // 如果 ransomNote 的长度大于 magazine 的长度，则返回 false
    Map<Character,Integer> map = new HashMap<>(); // 使用哈希表来记录 magazine 中每个字符的出现次数
    for(char c: magazine.toCharArray()){
        map.put(c,map.getOrDefault(c,0) + 1); // 将 magazine 中的每个字符及其出现次数添加到哈希表中
    }
    for (char c : ransomNote.toCharArray()) {
        if (map.getOrDefault(c, 0) == 0) { // 如果该字符在哈希表中不存在或出现次数为0，则返回 false
            return false;
        } else {
            map.put(c, map.get(c) - 1); // 如果该字符在哈希表中存在且出现次数大于0，则将该字符的出现次数减1
        }
    }
    return true; // 如果遍历完 ransomNote 中的所有字符后，哈希表中所有字符的出现次数都为0，则返回 true
}