哈希
更新: 8/26/2025 字数: 0 字 时长: 0 分钟
两数之和
java
/**
* <p>采用暴力枚举法，通过双重循环遍历所有可能的数对。</p>
*
* <h3>优化关键点：</h3>
* <ul>
* <li><strong>无优化：</strong> 这是最直接但效率最低的解法。</li>
* <li><strong>双重循环：</strong> 通过嵌套循环遍历所有组合，确保 {@code j} 始终大于 {@code i} 以避免重复和自身相加。</li>
* </ul>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(n^2)} - 外层循环 {@code n} 次，内层循环平均 {@code n/2} 次。</li>
* <li><strong>空间复杂度：</strong> {@code O(1)} - 除了存储输入和输出，没有使用额外的辅助空间。</li>
* </ul>
*
* @param nums 输入整数数组。
* @param target 目标和。
* @return 包含两个数索引的数组，如果不存在则返回空数组。
*/
public int[] twoSum(int[] nums, int target) {
int n = nums.length; // 获取数组长度
// 外层循环：遍历数组中的每一个元素作为第一个加数 (nums[i])
// i 从 0 遍历到倒数第二个元素，因为 j 会从 i+1 开始
for (int i = 0; i < n - 1; i++) {
// 内层循环：遍历 i 之后的每一个元素作为第二个加数 (nums[j])
// 确保 j > i，避免重复组合和自身相加
for (int j = i + 1; j < n; j++) {
// 检查当前两个元素的和是否等于目标值 target
if (nums[i] + nums[j] == target) {
// 如果找到，立即返回这两个元素的索引
return new int[]{i, j};
}
}
}
// 如果遍历完所有组合都没有找到，返回一个空数组（表示无解）
return new int[0];
}java
/**
* <p>采用暴力枚举法，略微改变内层循环的遍历方向，但本质仍是 O(n^2)。</p>
*
* <h3>优化关键点：</h3>
* <ul>
* <li><strong>时间复杂度上无本质优化：</strong> 仍然是 {@code O(n^2)}。</li>
* <li><strong>思维上的调整：</strong> 先确定当前数 {@code currentNum} 和补数 {@code complement}，然后尝试在之前遍历过的元素中查找 {@code complement}。这为哈希表解法奠定了思路基础。</li>
* </ul>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(n^2)} - 外层循环 {@code n} 次，内层循环平均 {@code n/2} 次。</li>
* <li><strong>空间复杂度：</strong> {@code O(1)} - 除了存储输入和输出，没有使用额外的辅助空间。</li>
* </ul>
*
* @param nums 输入整数数组。
* @param target 目标和。
* @return 包含两个数索引的数组，如果不存在则返回空数组。
*/
public int[] twoSum(int[] nums, int target) {
// 外层循环：遍历数组中的每一个元素
for (int i = 0; i < nums.length; i++) {
// 当前元素的值
int currentNum = nums[i];
// 计算需要查找的“补数”
int complement = target - currentNum;
// 内层循环：遍历当前元素 (i) 之前的所有元素 (j)
// 查找是否存在一个元素 nums[j] 等于 complement
for (int j = 0; j < i; j++) { // 注意 j 的范围是 0 到 i-1
// 如果找到了补数
if (nums[j] == complement) {
// 返回补数的索引 j 和当前元素的索引 i
return new int[]{j, i};
}
}
}
// 如果遍历完所有组合都没有找到，返回一个空数组
return new int[0];
}java
/**
* <p>采用哈希表（{@code HashMap}）进行优化，将时间复杂度从 {@code O(n^2)} 降低到 {@code O(n)}。</p>
* <p>通过<strong>空间换时间</strong>的方式，实现单次遍历即可找到结果。</p>
*
* <h3>优化关键点：</h3>
* <ul>
* <li><strong>空间换时间：</strong> 使用 {@code HashMap} 存储已遍历的数字及其索引，避免重复计算。</li>
* <li><strong>O(1) 查找：</strong> {@code HashMap} 的 {@code containsKey()} 和 {@code get()} 操作平均时间复杂度为 {@code O(1)}。</li>
* <li><strong>单次遍历：</strong> 整个算法只需要遍历数组一次。在遍历过程中，每访问一个元素：
* <ol>
* <li>计算其补数 {@code complement = target - currentNum}。</li>
* <li>在 {@code HashMap} 中查找 {@code complement} 是否存在。</li>
* <li><strong>若存在：</strong> 说明已找到匹配项，立即返回补数的索引（{@code map.get(complement)}）和当前元素的索引（{@code i}）。</li>
* <li><strong>若不存在：</strong> 将当前元素 {@code currentNum} 及其索引 {@code i} 存入 {@code HashMap}，供后续元素查找。</li>
* </ol>
* </li>
* </ul>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(n)} - 数组单次遍历，{@code HashMap} 操作平均为 {@code O(1)}。</li>
* <li><strong>空间复杂度：</strong> {@code O(n)} - 最坏情况下，{@code HashMap} 可能存储数组中的所有 {@code n} 个元素。</li>
* </ul>
*
* @param nums 输入整数数组。
* @param target 目标和。
* @return 包含两个数索引的数组，如果不存在则返回空数组。
*/
public int[] twoSum(int[] nums, int target) {
// 创建一个 HashMap，用于存储“数字 -> 索引”的映射
// key 是数组中的数字，value 是该数字在数组中的索引
HashMap<Integer, Integer> map = new HashMap<>();
// 遍历数组中的每一个元素
for (int i = 0; i < nums.length; i++) {
// 当前遍历到的数字
int currentNum = nums[i];
// 计算当前数字的“补数”
int complement = target - currentNum;
// 检查 HashMap 中是否已经存在这个“补数”
if (map.containsKey(complement)) {
// 如果存在，说明我们找到了两个数：
// 1. 之前存入 HashMap 的 complement 对应的数字，其索引为 map.get(complement)
// 2. 当前遍历到的 currentNum，其索引为 i
return new int[]{map.get(complement), i};
}
// 如果 HashMap 中不存在 complement，
// 那么将当前数字 currentNum 及其索引 i 存入 HashMap
// 供后续的数字查找使用。
map.put(currentNum, i);
}
// 如果遍历完整个数组都没有找到，返回一个空数组（表示无解）
return new int[0];
}字母异位词分组
java
/**
* <h3>算法思路：</h3>
* <p>核心思想是如果两个字符串是字母异位词，那么它们排序后的字符串是完全相同的。</p>
* <ol>
* <li>创建一个 {@code HashMap}，其键（Key）是排序后的字符串，值（Value）是一个存储原始字符串的列表。</li>
* <li>遍历输入字符串数组 {@code strs} 中的每个字符串 {@code s}。</li>
* <li>将 {@code s} 转换为字符数组，并进行排序。</li>
* <li>将排序后的字符数组转换回字符串 {@code sortedStr}，作为哈希表的键。</li>
* <li>使用 {@code sortedStr} 去哈希表中查找。
* <ul>
* <li>如果 {@code sortedStr} 已经存在：将原始字符串 {@code s} 添加到其对应的列表中。</li>
* <li>如果 {@code sortedStr} 不存在：创建一个新的列表，添加 {@code s}，然后将 {@code sortedStr} 和新列表作为键值对存入哈希表。</li>
* </ul>
* </li>
* <li>最后，返回哈希表中所有值（即所有列表）的集合。</li>
* </ol>
*
* <h3>优化关键点：</h3>
* <ul>
* <li><strong>哈希表的使用：</strong> 通过将排序后的字符串作为哈希表的键，实现了 {@code O(1)} 平均时间复杂度的查找和插入，高效地将异位词归类。</li>
* <li><strong>排序作为标准化：</strong> 排序字符串是识别异位词的标准且简单的方法。</li>
* </ul>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(N * K log K)}
* <ul>
* <li>{@code N} 是输入数组 {@code strs} 的长度。</li>
* <li>{@code K} 是字符串的最大长度。</li>
* <li>对于每个字符串：
* <ul>
* <li>转换为字符数组：{@code O(K)}</li>
* <li>字符数组排序：{@code O(K log K)}</li>
* <li>构建哈希表键和查找/插入：平均 {@code O(K)} (取决于字符串哈希和比较，最坏 {@code O(K)} 如果键冲突严重，但在实际应用中通常接近 {@code O(1)})。</li>
* </ul>
* </li>
* <li>因此，总时间复杂度为 {@code N} 次 {@code K log K} 操作，即 {@code O(N * K log K)}。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(N * K)}
* <ul>
* <li>在最坏情况下，所有字符串都是唯一的（没有异位词），哈希表将存储 {@code N} 个键值对。</li>
* <li>每个键是长度为 {@code K} 的字符串，每个值是一个列表（平均存储一个字符串）。</li>
* <li>因此，总空间复杂度为 {@code O(N * K)}。</li>
* </ul>
* </li>
* </ul>
*
* @param strs 输入的字符串数组。
* @return 一个列表的列表，其中每个内部列表包含一组字母异位词。
*/
public List<List<String>> groupAnagrams(String[] strs) {
// 创建一个 HashMap，用于存储排序后的字符串作为键，以及对应的原始字符串列表作为值
// 例如：{"aet": ["eat", "tea", "ate"], "ant": ["tan", "nat"], "abt": ["bat"]}
HashMap<String, List<String>> map = new HashMap<>();
// 遍历输入字符串数组
for (String s : strs) {
// 将当前字符串转换为字符数组
char[] charArray = s.toCharArray();
// 对字符数组进行排序
Arrays.sort(charArray);
// 将排序后的字符数组转换回字符串，作为哈希表的键
String sortedStr = new String(charArray);
// 如果哈希表中不存在这个排序后的字符串作为键
if (!map.containsKey(sortedStr)) {
// 则创建一个新的列表，并将其作为值与 sortedStr 关联
map.put(sortedStr, new ArrayList<>());
}
// 将原始字符串 s 添加到对应 sortedStr 的列表中
map.get(sortedStr).add(s);
}
// 最后，返回哈希表中所有值（即所有分组的列表）的集合
// new ArrayList<>(map.values()) 将 Map 的所有值收集到一个新的 List 中
return new ArrayList<>(map.values());
}最长连续序列
java
/**
* <h3>算法思路：</h3>
* <p>为了达到 O(n) 的时间复杂度，我们采用哈希集合来快速判断数字是否存在，并优化序列的查找方式。</p>
* <ol>
* <li><strong>去重与快速查找：</strong> 将所有输入数字存入一个 {@code HashSet}。这允许我们在 {@code O(1)} 平均时间复杂度内检查一个数字是否存在。</li>
* <li><strong>寻找序列起点：</strong> 遍历 {@code HashSet} 中的每个数字 {@code num}。我们只对那些可能是<strong>连续序列起点</strong>的数字感兴趣。
* <ul>
* <li>如果 {@code num - 1} 存在于 {@code HashSet} 中，说明 {@code num} 不是一个新序列的起点（它属于以 {@code num - 1} 开头的某个序列），我们直接跳过它，因为它会在其真正的起点处被处理。</li>
* <li>如果 {@code num - 1} 不存在于 {@code HashSet} 中，那么 {@code num} 就是一个潜在的最长连续序列的起点。</li>
* </ul>
* </li>
* <li><strong>扩展序列：</strong> 当找到一个序列起点 {@code num} 时，我们开始向右（即递增方向）查找连续的数字。
* <ul>
* <li>初始化当前序列长度 {@code currentLength = 1}。</li>
* <li>从 {@code currentNum = num + 1} 开始，不断检查 {@code currentNum} 是否存在于 {@code HashSet} 中。</li>
* <li>如果存在，则 {@code currentLength} 加一，{@code currentNum} 也加一，继续查找。</li>
* <li>如果不存在，说明当前序列到此结束。</li>
* </ul>
* </li>
* <li><strong>更新最长长度：</strong> 每次找到一个序列的长度后，更新全局最大长度 {@code maxLength}。</li>
* </ol>
*
* <h3>优化关键点：</h3>
* <ul>
* <li><strong>哈希集合：</strong> 提供 {@code O(1)} 平均时间复杂度的查找能力，避免了排序或嵌套循环带来的高复杂度。</li>
* <li><strong>跳过非起点元素：</strong> 关键优化在于，只从序列的起点开始扩展。如果一个数字 {@code x} 的前驱 {@code x-1} 存在，那么 {@code x} 肯定不是一个新序列的起点，因此跳过对它的处理，避免重复计算。每个数字只会被作为某个序列的“起点”进行一次处理（或者被跳过）。</li>
* </ul>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(n)}
* <ul>
* <li>将所有数字存入 {@code HashSet}：{@code O(n)}。</li>
* <li>外层循环遍历 {@code HashSet} 中的所有 {@code n} 个数字。</li>
* <li>内层循环（扩展序列）：虽然是嵌套的，但每个数字（例如 {@code num}, {@code num+1}, {@code num+2}, ...）只会被 {@code contains} 操作访问<strong>常数次</strong>。具体来说，每个数字最多被作为“某个序列的起点”检查一次，被作为“某个序列的后续元素”检查一次。因此，所有内层循环的总操作次数加起来是线性的。</li>
* <li>综合起来，总时间复杂度为 {@code O(n)}。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(n)}
* <ul>
* <li>{@code HashSet} 在最坏情况下需要存储所有 {@code n} 个不重复的数字。</li>
* </ul>
* </li>
* </ul>
*
* @param nums 未排序的整数数组。
* @return 最长数字连续序列的长度。
*/
public int longestConsecutive(int[] nums) {
// 如果数组为空，直接返回 0
if (nums == null || nums.length == 0) {
return 0;
}
// 1. 将所有数字存入哈希集合，以便 O(1) 查找
Set<Integer> numSet = new HashSet<>();
for (int num : nums) {
numSet.add(num);
}
int maxLength = 0; // 记录找到的最长连续序列的长度
// 2. 遍历哈希集合中的每个数字
for (int num : numSet) {
// 3. 判断当前数字是否是一个连续序列的起点
// 如果 num - 1 存在于集合中，说明 num 不是起点，它只是某个更长序列的中间部分，跳过它
if (!numSet.contains(num - 1)) {
// 如果 num - 1 不存在，则 num 是一个新序列的起点
int currentNum = num; // 当前正在检查的数字
int currentLength = 1; // 当前序列的长度
// 4. 从起点开始，向右扩展序列
while (numSet.contains(currentNum + 1)) {
currentNum++; // 继续检查下一个连续数字
currentLength++; // 序列长度增加
}
// 5. 更新最长序列长度
maxLength = Math.max(maxLength, currentLength);
}
}
return maxLength;
}贡献者
LI SIR