面试经典 150 题-哈希表

LeetCode 面试经典 150 题-哈希表

赎金信

哈希表

  1. 对magzine中的字符做统计。
  2. 遍历ransomNote字符串，对出现的字符，哈希表-1，如果出现小于0的情况则返回false，否则最后返回true。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] cnt = new int[26];
        // 对于magazine
        for (int i = 0; i < magazine.length(); i++) {
            cnt[magazine.charAt(i) - 'a']++;
        }
        // 对于ransomNote
        for (int i = 0; i < ransomNote.length(); i++) {
            cnt[ransomNote.charAt(i) - 'a']--;
            if (cnt[ransomNote.charAt(i) - 'a'] < 0) {
                return false;
            }
        }

        return true;        
    }
}
  • 时间复杂度：O(m + n)
  • 空间复杂度：$O(|\Sigma|)$

同构字符串

哈希表

考虑统计两字符串不同字符的个数，经测试会有测试点不通过：s =”bbbaaaba”，t =”aaabbbba”。t =
“aaabbbba”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public boolean isIsomorphic(String s, String t) {
        int[] hash = new int[128];
        // 对于字符串s
        int cntS = 0;
        for (int i = 0; i < s.length(); i++) {
            if (hash[s.charAt(i)] == 0) {
                cntS++;
            }
            hash[s.charAt(i)]++;
        }
        // 对于t
        Arrays.fill(hash, 0);
        int cntT = 0;
        for (int i = 0; i < t.length(); i++) {
            if (hash[t.charAt(i)] == 0) {
                cntT++;
            }
            hash[t.charAt(i)]++;
        }
        // 比较
        return cntS == cntT;
    }
}
  1. 维护两张哈希表，第一张哈希表 s2t 以 s 中字符为键，映射至 t 的字符为值，第二张哈希表 t2s 以 t 中字符为键，映射至 s 的字符为值。
  2. 从左至右遍历两个字符串的字符，不断更新两张哈希表，如果出现冲突（即当前下标 index 对应的字符 s[index] 已经存在映射且不为 t[index] 或当前下标 index 对应的字符 t[index] 已经存在映射且不为 s[index]）时说明两个字符串无法构成同构，返回 false。
  3. 如果遍历结束没有出现冲突，则表明两个字符串是同构的，返回 true 即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public boolean isIsomorphic(String s, String t) {
        Map<Character, Character> s2t = new HashMap<>();
        Map<Character, Character> t2s = new HashMap<>();

        int n = s.length();
        for (int i = 0; i < n; i++) {
            char x = s.charAt(i);
            char y = t.charAt(i);
            if ((s2t.containsKey(x) && s2t.get(x) != y) || (t2s.containsKey(y) && t2s.get(y) != x)) {
                return false;
            }
            s2t.put(x, y);
            t2s.put(y, x);
        }

        return true;
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：$O(|\Sigma|)$

单词规律

哈希表

与上一题类似，但对应关系变为character -> string。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public boolean wordPattern(String pattern, String s) {
        // 使用正则表达式分割以避免多个空格问题
        String[] words = s.split("\\s+");
        
        // 长度不一致直接返回 false
        if (pattern.length() != words.length) {
            return false;
        }

        // 定义两个映射：字符到字符串和字符串到字符的映射
        Map<Character, String> p2s = new HashMap<>();
        Map<String, Character> s2p = new HashMap<>();

        // 遍历模式字符串中的每个字符和对应的单词
        for (int i = 0; i < pattern.length(); i++) {
            char x = pattern.charAt(i);  // 当前模式字符
            String y = words[i];  // 当前对应的单词

            // 检查映射是否冲突
            if (p2s.containsKey(x) && !p2s.get(x).equals(y) || s2p.containsKey(y) && !s2p.get(y).equals(x)) {
                return false;
            }

            // 更新映射
            p2s.put(x, y);
            s2p.put(y, x);
        }

        return true;
    }
}

注意判断字符串是否相等要用.equals方法而不能直接用==。

  • 时间复杂度：O(m + n)
  • 空间复杂度：O(m + n)，最坏情况下，我们需要存储 pattern 中的每一个字符和 str 中的每一个字符串。

有效的字母异位词

哈希表

判断两个字符串的哈希情况是否一致。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public boolean isAnagram(String s, String t) {
        int m = s.length();
        int n = t.length();
        if (m != n) {
            return false;
        }

        int[] hash = new int[26];
        // 统计s
        for (int i = 0; i < m; i++) {
            hash[s.charAt(i) - 'a']++;
        }
        // 统计t
        for (int i = 0; i < n; i++) {
            hash[t.charAt(i) - 'a']--;
            if (hash[t.charAt(i) - 'a'] < 0) {
                return false;
            }
        }

        //检查
        for (int i = 0; i < 26; i++) {
            if (hash[i] != 0) {
                return false;
            }
        } 
        return true;
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：$O(|\Sigma|)$

字母异位词分组

排序

  1. 把每个单词进行排序，将排序后的字符串作为键，字符串作为值加入到该键对应的字符串数组中。
  2. 遍历上面的哈希表，加入结果集。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        // 定义哈希表
        Map<String, List<String>> hash = new HashMap<>();
        for (String str : strs) {
            // 排序
            char[] charArray = str.toCharArray();
            Arrays.sort(charArray);
            String sortedStr = new String(charArray);
            // 加入哈希表
            if (!hash.containsKey(sortedStr)) {
                hash.put(sortedStr, new ArrayList<>());
            }
            // 将当前字符串加入到对应的 List 中
            hash.get(sortedStr).add(str);
        }
        // 返回结果
        return new ArrayList<>(hash.values());
    }
}
  • 时间复杂度：O(nklogk)，其中 n 是 strs 中的字符串的数量，k 是 strs 中的字符串的的最大长度。
  • 空间复杂度：O(nk)

计数

  1. 对于每个字符串，首先使用哈希表统计每个字母出现的频率，然后将频率表转换为字符串作为键。
  2. 这样处理完之后就得到与上一种方法类似的哈希表。最后将哈希表中的结果移到结果数组中。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        // 定义哈希表
        Map<String, List<String>> hash = new HashMap<>();
        for (String str : strs) {
            // 统计
            int[] cnt = new int[26];
            for (int i = 0; i < str.length(); i++) {
                cnt[str.charAt(i) - 'a']++;
            }
            // 拼接成字符串
            StringBuffer sb = new StringBuffer();
            for (int i = 0; i < 26; i++) {
                sb.append(cnt[i]);
                sb.append('#');
            }
            // 加入哈希表
            String key = sb.toString();
            if (!hash.containsKey(key)) {
                hash.put(key, new ArrayList<String>());
            }
            hash.get(key).add(str);
        }
        
        // 返回结果
        return new ArrayList<>(hash.values());
    }
}
  • 时间复杂度：O(n(k+∣Σ∣))
  • 空间复杂度：O(n(k+∣Σ∣))

四数之和

排序+双指针

之前做过两数、三数之和，四数之和与三数之和的思路类似，都是先排序，固定数，然后剩下两个数利用双指针找。

  • 每一种循环枚举到的下标必须大于上一重循环枚举到的下标；
  • 同一重循环中，如果当前元素与上一个元素相同，则跳过当前元素。

一些剪枝操作：

  • 在确定第一个数之后，如果 nums[i]+nums[i+1]+nums[i+2]+nums[i+3]>target，说明此时剩下的三个数无论取什么值，四数之和一定大于 target，因此退出第一重循环；
  • 在确定第一个数之后，如果 nums[i]+nums[n−3]+nums[n−2]+nums[n−1]<target，说明此时剩下的三个数无论取什么值，四数之和一定小于 target，因此第一重循环直接进入下一轮，枚举 nums[i+1]；
  • 在确定前两个数之后，如果 nums[i]+nums[j]+nums[j+1]+nums[j+2]>target，说明此时剩下的两个数无论取什么值，四数之和一定大于 target，因此退出第二重循环；
  • 在确定前两个数之后，如果 nums[i]+nums[j]+nums[n−2]+nums[n−1]<target，说明此时剩下的两个数无论取什么值，四数之和一定小于 target，因此第二重循环直接进入下一轮，枚举 nums[j+1]。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<>();
        int n = nums.length;
        if (n < 4) {
            return res;
        }
        // 排序
        Arrays.sort(nums);
        // 确定第一个数
        for (int i = 0; i < n - 3; i++) {
            // 剪枝，跳过重复元素
            if (i > 0 && nums[i] == nums[i-1]) {
                continue;
            }
            // 剪枝，大于目标
            if ((long) nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target) {
                break;
            }
            // 剪枝，小于目标
            if ((long) nums[i] + nums[n-3] + nums[n-2] + nums[n-1] < target) {
                continue;
            }
            // 确定第二个数
            for (int j = i + 1; j < n - 2; j++) {
                // 剪枝，跳过重复元素
                if (j > i + 1 && nums[j] == nums[j-1]) {
                    continue;
                }
                // 剪枝，大于目标
                if ((long) nums[i] + nums[j] + nums[j+1] + nums[j+2] > target) {
                    break;
                } 
                // 剪枝，小于目标
                if ((long) nums[i] + nums[j] + nums[n-2] + nums[n-1] < target) {
                    continue;
                }
                // 双指针寻找第三、四个数
                int left = j + 1, right = n - 1;
                while (left < right) {
                    long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum == target) {
                        res.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        // 跳过重复元素
                        while (left < right && nums[left] == nums[left+1]) {
                            left++;
                        }
                        left++;
                        while (left < right && nums[right] == nums[right-1]) {
                            right--;
                        }
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        right--;
                    }
                }
            }
        }

        return res;
    }
}
  • 时间复杂度：$O(n^3)$
  • 空间复杂度：O(logn)

注意求和的地方需要转为long，否则会溢出。

快乐数

哈希表

不断对数字的每一位进行平方求和，如果这个数不是快乐数，那么它一定会产生循环。使用哈希表存储已经访问过的情况，如果再次遇到这个数字，就说明出现循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public boolean isHappy(int n) {
        Set<Integer> set = new HashSet<>();
        set.add(n);
        while (n != 1) {
            int num = 0;
            while (n != 0) {
                num += (n % 10) * (n % 10);
                n /= 10;
            }
            n = num;
            if (set.contains(n)) {
                return false;
            }
            set.add(n);
        }
        return true;
    }
}
  • 时间复杂度：O(logn)
  • 空间复杂度：O(logn)

快慢指针法

可以看成是链表，起始数字是链表的头 “节点”，链中的所有其他数字都是节点。问题就可以转换为检测一个链表是否有环。因此我们在这里可以使用弗洛伊德循环查找算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public boolean isHappy(int n) {
        int slow = n, fast = getNext(n);
        while (fast != 1 && slow != fast) {
            slow = getNext(slow);
            fast = getNext(getNext(fast));
        }
        return fast == 1;
    }

    public int getNext(int n) {
        int num = 0;
        while (n > 0) {
            int d = n % 10;
            n /= 10;
            num += d * d;
        }
        return num;
    }
}
  • 时间复杂度：O(logn)
  • 空间复杂度：O(1)

存在重复元素II

哈希表

一边遍历数组，一边把索引存到哈希表中。如果当前元素已经存在于哈希表，则判断其索引值之差的绝对值是否小于等于k，如果小于直接返回true，否则更新索引为当前元素下标，因为需要索引差尽可能接近。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        int n = nums.length;
        Map<Integer, Integer> hash = new HashMap<>();
        for (int i = 0; i < n; i++) {
            if (hash.containsKey(nums[i]) && Math.abs(i - hash.get(nums[i])) <= k) {
                return true;
            }
            hash.put(nums[i], i);
        }
        return false;
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

滑动窗口

考虑数组 nums 中的每个长度不超过 k+1 的滑动窗口，同一个滑动窗口中的任意两个下标差的绝对值不超过 k。如果存在一个滑动窗口，其中有重复元素，则存在两个不同的下标 i 和 j 满足 nums[i]=nums[j] 且 ∣i−j∣≤k。如果所有滑动窗口中都没有重复元素，则不存在符合要求的下标。因此，只要遍历每个滑动窗口，判断滑动窗口中是否有重复元素即可。

如果一个滑动窗口的结束下标是 i，则该滑动窗口的开始下标是 max(0,i−k)。可以使用哈希集合存储滑动窗口中的元素。从左到右遍历数组 nums，当遍历到下标 i 时，具体操作如下：

  • 如果 i>k，则下标 i−k−1 处的元素被移出滑动窗口，因此将 nums[i−k−1] 从哈希集合中删除；
  • 判断 nums[i] 是否在哈希集合中，如果在哈希集合中则在同一个滑动窗口中有重复元素，返回 true，如果不在哈希集合中则将其加入哈希集合。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        int n = nums.length;
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < n; i++) {
            // 维护滑动窗口
            if (i > k) {
                set.remove(nums[i-k-1]);
            }
            // 已经存在就返回true
            if (!set.add(nums[i])) {
                return true;
            }
        }
        return false;
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(k)

最长连续序列

哈希表

  1. 用集合进行去重
  2. 遍历集合：
  • 确定序列起始，即判断当前数字-1是否存在于集合中，如果不存在，则当前数字就是序列起始；
  • 更新连续序列长度；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        // 将元素加入集合
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            set.add(nums[i]);
        }
        // 遍历集合
        int ans = 0;
        for (int num : set) {
            // 确定当前序列起始
            if (!set.contains(num - 1)) {
                int curNum = num, curLen = 1;
                while (set.contains(curNum + 1)) {
                    curNum++;
                    curLen++;
                }
                ans = Math.max(ans, curLen);
            }
        }

        return ans;

    }
}
  • 时间复杂度：O(n)，外层循环需要 O(n) 的时间复杂度，只有当一个数是连续序列的第一个数的情况下才会进入内层循环，然后在内层循环中匹配连续序列中的数，因此数组中的每个数只会进入内层循环一次。
  • 空间复杂度：O(n)

补充

Java的集合（Collection）是Java提供的一种数据结构，用于存储和操作数据。集合框架提供了一种高效、灵活的方式来处理对象的数据，可以替代数组等传统的数据结构。Java集合框架包括了各种不同的接口和类，可以满足不同的数据存储和操作需求。

Java集合框架的核心接口包括：

1. Collection接口

Collection是所有集合类的根接口。它定义了常见的集合操作，如添加、删除、迭代等。Collection接口的子接口包括Set、List、Queue等。

2. List接口

List是一个有序的集合，允许元素重复。元素可以根据索引访问。List接口的常见实现类有：

  • ArrayList：基于动态数组实现，支持快速随机访问，但在插入或删除元素时性能较差。
  • LinkedList：基于双向链表实现，插入和删除操作较快，但访问元素时速度较慢。
  • Vector：类似于ArrayList，但它是同步的，因此线程安全，性能相对较差，通常不推荐使用。

3. Set接口

Set是一个不允许重复元素的集合。Set接口的常见实现类有：

  • HashSet：基于哈希表实现，插入和查找效率较高，但元素的顺序是不确定的。
  • LinkedHashSet：基于哈希表和链表实现，保证元素的插入顺序。
  • TreeSet：基于红黑树实现，支持排序和快速查找。

4. Queue接口

Queue是一个按先进先出（FIFO）原则处理元素的集合。它适合用来实现任务调度、消息队列等。常见的Queue实现类有：

  • LinkedList：既是List的实现类，又实现了Queue接口，可以作为队列使用。
  • PriorityQueue：基于优先级堆实现，队列中的元素按优先级顺序排列。

Deque（双端队列，Double-Ended Queue）是一个允许在两端（头部和尾部）进行插入和删除操作的队列。与传统的队列（Queue）不同，Deque 允许在两端进行插入和删除，因此它既可以作为队列（FIFO）使用，也可以作为栈（LIFO）使用。

在 Java 中，Deque 是 java.util 包下的一个接口，继承自 Queue，并提供了双端队列的相关方法。它的常见实现类包括 ArrayDeque 和 LinkedList。

5. Map接口

Map是一个映射关系接口，用于存储键值对（key-value）。Map不继承自Collection接口，因此是一个独立的接口。Map接口的常见实现类有：

  • HashMap：基于哈希表实现，允许null作为键和值，元素无顺序保证。
  • LinkedHashMap：与HashMap类似，但保持插入顺序。
  • TreeMap：基于红黑树实现，键值对按键的自然顺序或自定义顺序排序。
  • Hashtable：类似于HashMap，但它是同步的，因此线程安全，但性能较差，通常不推荐使用。

6. SortedSet和SortedMap接口

SortedSet和SortedMap接口分别是Set和Map的有序版本，提供对元素的排序支持。

  • SortedSet：如TreeSet，可以保证集合中的元素有序。
  • SortedMap：如TreeMap，可以保证Map中的键有序。

7. Iterator接口

Iterator接口用于遍历集合中的元素。几乎所有的集合都提供了iterator()方法，返回一个Iterator对象。Iterator有三大方法：

  • hasNext()：检查是否有下一个元素。
  • next()：返回下一个元素。
  • remove()：移除当前元素（仅在支持此操作的集合中有效）。

8. 常见的集合操作

集合框架提供了多种操作数据的方法，常见的操作包括：

  • 添加元素：add(E e)（Set、List等），put(K key, V value)（Map）。
  • 删除元素：remove(Object o)（Set、List等），remove(Object key)（Map）。
  • 查找元素：contains(Object o)（Set、List等），containsKey(Object key)（Map）。
  • 遍历元素：使用Iterator接口或增强for循环。
  • 大小：size()。
  • 清空集合：clear()。

9. 集合与泛型

Java集合框架广泛使用了泛型，使得集合能够存储任何类型的对象，并且能够在编译时提供类型检查。例如：

1
2
3
List<String> list = new ArrayList<>();
list.add("Hello");
list.add("World");

上面的代码使用了泛型，List只能存储String类型的数据，避免了类型转换错误。

10. 集合工具类

Collections类是一个工具类，提供了多种静态方法来操作集合，例如排序、查找、反转等。

  • Collections.sort(List<T> list)：对List进行排序。
  • Collections.shuffle(List<?> list)：对List进行随机打乱。
  • Collections.reverse(List<?> list)：反转List的元素顺序。
  • Collections.max(Collection<? extends T> coll)：返回集合中的最大元素。

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import java.util.*;

public class CollectionExample {
    public static void main(String[] args) {
        // 使用ArrayList（实现了List接口）
        List<String> list = new ArrayList<>();
        list.add("Java");
        list.add("Python");
        list.add("C++");
        System.out.println("List: " + list);

        // 使用HashSet（实现了Set接口）
        Set<String> set = new HashSet<>();
        set.add("Apple");
        set.add("Banana");
        set.add("Apple");  // 重复元素不会被添加
        System.out.println("Set: " + set);

        // 使用HashMap（实现了Map接口）
        Map<String, Integer> map = new HashMap<>();
        map.put("Alice", 30);
        map.put("Bob", 25);
        map.put("Charlie", 35);
        System.out.println("Map: " + map);

        // 使用PriorityQueue（实现了Queue接口）
        Queue<Integer> queue = new PriorityQueue<>();
        queue.add(5);
        queue.add(2);
        queue.add(8);
        System.out.println("Queue: " + queue);

        // 遍历集合
        System.out.println("Iterating over list:");
        for (String item : list) {
            System.out.println(item);
        }
    }
}

总结

Java集合框架提供了丰富的数据结构和接口，能够满足不同的应用场景。选择合适的集合类型和方法，可以提高代码的效率和可读性。在实际开发中，合理地选择合适的集合类型及其操作是非常重要的。

算法笔记 > 哈希表
#哈希表
面试经典 150 题-哈希表
http://example.com/2025/01/06/posts/hot150-5/
作者
Xuan Yang
发布于
2025年1月6日
许可协议