哈希表示例

示例1

两数之和

"两数之和"（Two Sum）是LeetCode上的一个经典算法问题，编号为1，它要求在一个整数数组nums中找到两个不同的索引i和j，使得nums[i] + nums[j] == target。

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

import java.util.HashMap;
import java.util.Map;public class TwoSum {public static 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);}throw new IllegalArgumentException("No two sum solution");}public static void main(String[] args) {int[] nums = {2, 7, 11, 15};int target = 9;int[] result = twoSum(nums, target);System.out.println(Arrays.toString(result)); // 输出: [0, 1]}
}

详细说明：

使用 HashMap 来存储数组中的元素及其对应的索引。
遍历数组，对于每个元素，计算其补数（即 target - nums[i]）。
检查 HashMap 中是否存在该补数，如果存在，则找到了两个数，它们的和为 target。
如果不存在，则将当前元素及其索引存入 HashMap 中。
该算法的时间复杂度为 O(n)，因为只需遍历数组一次。

示例2

四数之和

"四数之和"（4Sum）是LeetCode上的一个经典算法问题，编号为18。该问题要求在一个整数数组nums中找到所有不重复的四个元素组合，使得这四个元素之和等于给定的目标值target。

问题描述：给定四个整数数组A, B, C, D，计算有多少个元组 (i, j, k, l) 使得 A[i] + B[j] + C[k] + D[l] = 0。

import java.util.HashMap;
import java.util.Map;public class FourSumII {public static int fourSumCount(int[] A, int[] B, int[] C, int[] D) {Map<Integer, Integer> map = new HashMap<>();for (int a : A) {for (int b : B) {map.put(a + b, map.getOrDefault(a + b, 0) + 1);}}int count = 0;for (int c : C) {for (int d : D) {count += map.getOrDefault(-(c + d), 0);}}return count;}public static void main(String[] args) {int[] A = {1, 2};int[] B = {-2, -1};int[] C = {-1, 2};int[] D = {0, 2};System.out.println(fourSumCount(A, B, C, D)); // 输出: 2}
}

详细说明：

使用 HashMap 来存储数组 A 和 B 中所有可能的两数之和及其出现次数。
遍历数组 C 和 D，对于每一对 (c, d)，计算其补数 -(c + d)。
检查 HashMap 中是否存在该补数，如果存在，则将对应的出现次数累加到结果中。
该算法的时间复杂度为 O(n^2)，因为需要遍历两个数组的组合。

示例3

有效的字母异位位

在Java中，判断两个字符串是否为有效的字母异位词（Anagram），即这两个字符串是否由相同的字符组成，只是字符的排列顺序不同。

问题描述：给定两个字符串 s 和 t，编写一个函数来判断 t 是否是 s 的字母异位位。

import java.util.HashMap;
import java.util.Map;public class Anagram {public static boolean isAnagram(String s, String t) {if (s.length() != t.length()) {return false;}Map<Character, Integer> map = new HashMap<>();for (char c : s.toCharArray()) {map.put(c, map.getOrDefault(c, 0) + 1);}for (char c : t.toCharArray()) {if (!map.containsKey(c)) {return false;}map.put(c, map.get(c) - 1);if (map.get(c) < 0) {return false;}}return true;}public static void main(String[] args) {String s = "anagram";String t = "nagaram";System.out.println(isAnagram(s, t)); // 输出: true}
}

详细说明：

使用 HashMap 来记录字符串 s 中每个字符的出现次数。
遍历字符串 t，对于每个字符，检查 HashMap 中是否存在该字符，如果不存在则返回 false。
如果存在，则将对应的出现次数减一，如果出现次数小于零则返回 false。
最后，如果所有字符都匹配，则返回 true。
该算法的时间复杂度为 O(n)，因为只需遍历两个字符串一次。

示例4

赎金信

在Java中解决“赎金信”问题（LeetCode 383题），核心任务是判断一个字符串ransomNote是否可以完全由另一个字符串magazine中的字符构成。这个问题的背景设定是为了不在赎金信中暴露字迹，需要从杂志上搜索各个需要的字母，组成单词来表达意思。每个字符只能使用一次，即magazine中的字符不能被重复利用。

问题描述：给定两个字符串 ransomNote 和 magazine，判断 ransomNote 是否可以由 magazine 中的某些字符组成。

import java.util.HashMap;
import java.util.Map;public class RansomNote {public static boolean canConstruct(String ransomNote, String magazine) {Map<Character, Integer> map = new HashMap<>();for (char c : magazine.toCharArray()) {map.put(c, map.getOrDefault(c, 0) + 1);}for (char c : ransomNote.toCharArray()) {if (!map.containsKey(c) || map.get(c) == 0) {return false;}map.put(c, map.get(c) - 1);}return true;}public static void main(String[] args) {String ransomNote = "a";String magazine = "b";System.out.println(canConstruct(ransomNote, magazine)); // 输出: false}
}

详细说明：

使用 HashMap 来记录字符串 magazine 中每个字符的出现次数。
遍历字符串 ransomNote，对于每个字符，检查 HashMap 中是否存在该字符且出现次数大于零，如果不存在或出现次数为零则返回 false。
如果存在，则将对应的出现次数减一。
最后，如果所有字符都匹配，则返回 true。
该算法的时间复杂度为 O(n)，因为只需遍历两个字符串一次。