【Java完整版面试必备】Leetcode Top100题目和答案-哈希

何遇mirror

10530人浏览 · 2024-07-01 10:12:16

何遇mirror · 2024-07-01 10:12:16 发布

以下摘自leetcode Top100精选题目-哈希

1. 两数之和

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例:

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

Solution:

可以通过使用哈希表来解决，从而将时间复杂度降低到O(n)。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        // 创建一个哈希表，用来存储已遍历过的数字及其对应的索引
        Map<Integer, Integer> numMap = new HashMap<>();
        
        // 遍历数组
        for (int i = 0; i < nums.length; i++) {
            // 计算当前数字与目标值之间的差值
            int complement = target - nums[i];
            
            // 如果差值已经在哈希表中，则说明我们找到了一对解
            if (numMap.containsKey(complement)) {
                // 返回这对解的索引
                return new int[]{numMap.get(complement), i};
            }
            
            // 将当前数字及索引存入哈希表，以便后续查找
            numMap.put(nums[i], i);
        }
        
        // 如果没有找到符合条件的数对，则返回空数组（本题假设一定有解，所以这里理论上不会执行）
        return new int[0];
    }
}

创建了一个哈希表numMap，用于存储已经遍历过的每个数字及其对应的索引。然后遍历整个数组nums，对于每个遍历到的数字nums[i]，计算它与目标值target之间的差值complement，并检查这个差值是否已经在哈希表中。如果差值存在，就说明找到了两个数，它们的和为目标值，直接返回这两个数的索引。如果差值不在哈希表中，则将当前数字及其索引存入哈希表，继续遍历。这样，只需要遍历一次数组即可找到答案。

49. 字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

Solution:

public class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        if (strs == null || strs.length == 0) {
            return new ArrayList<>();
        }
        
        // 使用HashMap存储字母异位词分组，键为排序后的字符串，值为该字母异位词组的列表
        Map<String, List<String>> anagramGroups = new HashMap<>();

        for (String str : strs) {
            // 对当前字符串排序，得到排序后的字符串作为哈希表的键
            char[] charArray = str.toCharArray();
            Arrays.sort(charArray);
            String sortedStr = new String(charArray);

            // 如果排序后的字符串已经在哈希表中，则将当前字符串添加到对应的列表中
            if (!anagramGroups.containsKey(sortedStr)) {
                anagramGroups.put(sortedStr, new ArrayList<>());
            }
            anagramGroups.get(sortedStr).add(str);
        }

        // 将哈希表的值（即所有字母异位词分组）收集到一个List中并返回
        return new ArrayList<>(anagramGroups.values());
    }
}

先检查输入是否为空，遍历给定的字符串数组。对于每一个字符串，将其字符排序后得到一个新的字符串，用作哈希表的键。如果这个键不存在于哈希表中，则创建一个新的列表作为值；如果键已存在，则将当前字符串添加到对应的列表中。将哈希表中的所有值（即所有字母异位词的分组）收集到一个新的列表中并返回。这种方法的时间复杂度主要取决于排序操作，对于每个字符串来说是O(nlogn)，其中n是字符串的最大长度，总的时间复杂度接近O(m*nlogn)，m为字符串数组的长度。

128. 最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例:

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

Solution:

import java.util.HashSet;
import java.util.Set;

public class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        Set<Integer> numSet = new HashSet<>();
        for (int num : nums) {
            numSet.add(num);
        }

        int maxLength = 0;

        for (int num : numSet) {
            // 只有当num-1不存在时，才认为num是新序列的起点
            if (!numSet.contains(num - 1)) {
                int currentNum = num;
                int currentLength = 1;

                // 向序列右侧扩展
                while (numSet.contains(currentNum + 1)) {
                    currentNum++;
                    currentLength++;
                }

                // 更新最长序列长度
                maxLength = Math.max(maxLength, currentLength);
            }
        }

        return maxLength;
    }
}

将所有数组元素放入一个HashSet中，便于快速检查元素是否存在。遍历HashSet中的每个元素，对于每个元素，如果减一元素不存在于集合中，说明可以作为连续序列的起始点。通过不断检查并累加当前元素加一的值是否存在于集合中，来确定当前序列的长度。