LeetCode-Hot100-哈希表

前言

题单LeetCode 热题 100的哈希部分，给出解析。

1. Two Sum

题目描述

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution , and you may not use the same element twice.

You can return the answer in any order.

Constraints:

2 <= nums.length <= 10^4
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9
Only one valid answer exists.

Follow-up: Can you come up with an algorithm that is less than O(n^2) time complexity?

解题方法

使用一个哈希表存储数组中的元素及其索引。

key: 元素值；

value: 元素索引。

循环遍历数组，计算 target 与当前元素的差值，检查哈希表中是否存在差值，如果哈希表中存在差值，返回两个元素的索引。

如果没有找到差值，就将当前元素及其索引存入哈希表，继续遍历。

代码实现

Python版本：

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        num_to_index = {}
        for i, num in enumerate(nums):
            complement = target - num
            if complement in num_to_index:
                return [num_to_index[complement] , i]
            num_to_index[num] = i

Java版本：

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

复杂度分析

时间复杂度：$O(n)$，仅需遍历一次数组。

空间复杂度：$O(n)$，哈希表带来的额外存储空间。

49. Group Anagrams

原题链接

题目描述

Given an array of strings strs, group the anagrams together. You can return the answer in any order .

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Constraints:

1 <= strs.length <= 10^4
0 <= strs[i].length <= 100
strs[i] consists of lowercase English letters.

解题方法

要将给定的字符串数组按照字母异位词分组，可以利用字母异位词的一个性质：它们排序后会得到相同的字符串。基于此，我们可以将每个字符串排序后作为键，将其所有字母异位词放在同一个列表中，最后返回这些列表。

思路：

创建一个哈希表：
- key: 排序后的字符串；
- value: 包含这些字母异位词的列表。
遍历字符串数组，对每个字符串进行排序，将排序后的字符串作为键，将原字符串添加到对应的列表中。
返回哈希表中所有值的列表。

代码实现

Python版本：

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        anagrams = {}

        for s in strs:
            sorted_str = ''.join(sorted(s))

            if sorted_str not in anagrams:
                anagrams[sorted_str] = []
            anagrams[sorted_str].append(s)

        return list(anagrams.values())

Java版本：

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String,List<String>> hash_table = new HashMap<>();

        for(String s: strs){
            char[] chars = s.toCharArray();
            Arrays.sort(chars);
            String sortedStr = new String(chars);
            if(!hash_table.containsKey(sortedStr)){
                hash_table.put(sortedStr, new ArrayList<>());
            }
            hash_table.get(sortedStr).add(s);
        }

        return new ArrayList<>(hash_table.values());
    }
}

复杂度分析

时间复杂度：$O(nmlogm)$，其中 $n$ 为 $strs$ 的长度，$m$ 为 $strs[i]$ 的长度。

空间复杂度：$O(nm)$，哈希表带来的额外存储空间。

128. Longest Consecutive Sequence

原题链接

题目描述

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

Constraints:

0 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9

解题方法

这个问题要求我们在给定的未排序整数数组中，找到最长的连续元素序列的长度，并且算法的时间复杂度为 O(n)。

解决思路：

使用集合（Set）存储数组中的元素：
通过将所有元素存储在集合中，我们可以在 O(1) 的时间内判断一个元素是否存在。
遍历数组：
对于数组中的每一个数字，检查它是否是某个连续序列的起点。一个数字是序列的起点，当且仅当它的前一个数字（num - 1）不在集合中。
计算连续序列的长度：
如果找到一个序列的起点，继续检查这个起点之后的连续数字是否存在，并计算这个序列的长度。
更新最大长度：
在遍历过程中，记录遇到的最长序列的长度。
返回最长长度：
遍历完成后，返回记录的最长序列的长度。

代码实现

Python版本：

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        if not nums:
            return 0

        # 哈希表记录数组中的所有数
        num_set = set(nums)
        # 最长连续序列的长度
        longest_streak = 0

        for num in num_set:
            # 如果当前的数就是一个连续序列的起点，统计这个连续序列的长度
            if num - 1 not in num_set:
                current_num = num
                current_streak = 1
                # 不断查找连续序列，直到num的下一个数不存在于数组中
                while current_num + 1 in num_set:
                    current_num += 1
                    current_streak += 1

                longest_streak = max(longest_streak, current_streak)

        return longest_streak

Java版本：

class Solution {
    public int longestConsecutive(int[] nums) {
        if(nums.length == 0){
            return 0;
        }
        Set<Integer> num_set = new HashSet<>();
        for(int num : nums){
            num_set.add(num);
        }
        int long_streak = 0;

        for(int num : num_set){
            if(!num_set.contains(num - 1)){
                int current_num = num;
                int current_streak = 1;


            while(num_set.contains(current_num + 1)){
                current_num++;
                current_streak++;
            }
            long_streak = Math.max(long_streak, current_streak);
            }
        }

        return long_streak;
    }
}

复杂度分析

时间复杂度：$O(n)$，只需遍历一次序列。

空间复杂度：$O(n)$，哈希表带来的额外存储空间。