用Rust🦀写算法-哈希表篇

242. 有效的字母异位词

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

示例 1:

1
2
输入: s = "anagram", t = "nagaram"
输出: true

示例 2:

1
2
输入: s = "rat", t = "car"
输出:false

提示:

  • 1 <= s.length, t.length <= 5 * 104
  • s 和 t 仅包含小写字母

进阶: 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？

💡 思路：

  1. 哈希表法
  2. 数组记录法（输入字符串不能为unicode）

代码（思路一）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
use std::collections::HashMap;

impl Solution {
    pub fn is_anagram(s: String, t: String) -> bool {
        if s.len() != t.len() {
            return false;
        }
        let mut count = HashMap::new();

        for c in s.chars() {
            *count.entry(c).or_insert(0) += 1;
        }

        for c in t.chars() {
            let mut entry = count.entry(c).or_insert(0);
            *entry -= 1;
            if *entry < 0 {
                return false;
            }
        }

        true
    }
}

代码（思路二）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
use std::collections::HashMap;

impl Solution {
    pub fn is_anagram(s: String, t: String) -> bool {
        let mut cnt = [0; 26];
        for c in s.bytes() {
            cnt[(c - b'a') as usize] += 1;
        }
        for c in t.bytes() {
            cnt[(c - b'a') as usize] -= 1;
        }
        cnt.iter().all(|&x| x == 0)
    }
}

1002. 查找共用字符

给你一个字符串数组words，请你找出所有在words的每个字符串中都出现的共用字符（包括重复字符），并以数组形式返回。你可以按任意顺序返回答案。

示例 1：

1
2
输入：words = ["bella","label","roller"]
输出：["e","l","l"]

示例 2：

1
2
输入：words = ["cool","lock","cook"]
输出：["c","o"]

提示：

  • 1 <= words.length <= 100
  • 1 <= words[i].length <= 100
  • words[i] 由小写英文字母组成

💡 思路：

  1. 统计法
    a. 统计每个字符串字符出现的次数
    b. 取所有字符串中出现次数最少的
    c. 根据出现次数添加到结果数组中

代码（思路一）：

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
use std::collections::HashMap;
impl Solution {
    pub fn common_chars(words: Vec<String>) -> Vec<String> {
        if words.is_empty() {
            return vec![];
        }

        // 初始化最小频率表（用第一个单词）
        let mut min_freq = HashMap::new();
        for c in words[0].chars() {
            *min_freq.entry(c).or_insert(0) += 1;
        }

        // 与其他单词比较，取频率最小值
        for word in words.iter().skip(1) {
            let mut curr_freq = HashMap::new();
            for c in word.chars() {
                *curr_freq.entry(c).or_insert(0) += 1;
            }

            // 更新最小频率
            for (c, count) in min_freq.iter_mut() {
                *count = (*count).min(*curr_freq.get(c).unwrap_or(&0));
            }
        }

        // 转换为结果
        let mut result = Vec::new();
        for (c, &count) in min_freq.iter() {
            for _ in 0..count {
                result.push(c.to_string());
            }
        }

        result
    }
}

使用固定大小的数组（如 **[i32; 26]**）代替哈希表（如 **HashMap<char, i32>**）来统计字符频率可以显著优化性能：

1. 内存访问效率更高

  • 数组：连续内存布局，CPU 缓存命中率高（预取机制友好）
  • 哈希表：内存分散（需要处理哈希冲突和链表/开放寻址），缓存局部性差

2. 免去哈希计算开销

  • 数组：通过简单算术计算索引（(c - b'a') as usize）
  • 哈希表：每次操作都需要计算字符的哈希值（**HashMap** 默认使用 SipHash 算法，虽然安全但较慢）

3. 无动态分配开销

  • 数组：栈上分配（或编译器优化为寄存器操作）
  • 哈希表：需要堆内存分配（初始容量、扩容时的重新哈希）

4. 无冲突处理

  • 数组：直接访问确定位置，无冲突
  • 哈希表：需要处理哈希冲突（开放寻址/链表法）

5. 编译器优化更友好

  • 数组：固定大小循环易被展开（Loop Unrolling）
  • 哈希表：复杂逻辑阻碍优化（动态分派、边界检查等）

代码：

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
use std::collections::HashMap;
impl Solution {
    const size: usize = 26;
    pub fn common_chars(words: Vec<String>) -> Vec<String> {
        if words.is_empty() {
            return vec![];
        }

        let mut min_count = [0; Self::size];
        for c in words[0].bytes() {
            min_count[(c - b'a') as usize] += 1;
        }

        for s in words.iter().skip(1) {
            let mut count = [0; Self::size];
            for c in s.bytes() {
                count[(c - b'a') as usize] += 1;
            }

            for i in 0..Self::size {
                min_count[i] = min_count[i].min(count[i]);
            }
        }

        let mut res = Vec::new();
        for i in 0..Self::size {
            for _ in 0..min_count[i] {
                res.push(((i as u8 + b'a') as char).to_string());
            }
        }

        res
    }
}

349. 两个数组的交集

给定两个数组 nums1 和 nums2 ，返回 它们的 交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

示例 1：

1
2
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

示例 2：

1
2
3
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的

提示：

  • 1 <= nums1.length, nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 1000

💡 思路：HashSet：注意到题目中，输出结果唯一，不考虑结果顺序，第一想到的就是使用HashSet

代码（思路一）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
use std::collections::HashSet;

impl Solution {
    pub fn intersection(nums1: Vec<i32>, nums2: Vec<i32>) -> Vec<i32> {
        let mut res1 = HashSet::new();
        let mut res2 = HashSet::new();

        for n in nums1 {
            res1.insert(n);
        }

        for n in nums2 {
            res2.insert(n);
        }

        res1.intersection(&res2).cloned().collect()
    }
}

这里的代码有点丑陋，一点也不Rust，更改一下：

1
2
3
4
5
6
7
8
9
use std::collections::HashSet;

impl Solution {
    pub fn intersection(nums1: Vec<i32>, nums2: Vec<i32>) -> Vec<i32> {
        let set1: HashSet<_> = nums1.into_iter().collect();
        let set2: HashSet<_> = nums2.into_iter().collect();
        set1.intersection(&set2).cloned().collect()
    }
}

好一点了，不过创建了两个HashSet，还可以凹：

1
2
3
4
5
6
7
8
9
10
11
12
use std::collections::HashSet;

impl Solution {
    pub fn intersection(nums1: Vec<i32>, nums2: Vec<i32>) -> Vec<i32> {
        let set1: HashSet<i32> = nums1.into_iter().collect();
        nums2.into_iter()
            .filter(|x| set1.contains(x))
            .collect::<HashSet<_>>()
            .into_iter()
            .collect()
    }
}

再凹，一行代码写完：

1
2
3
4
5
6
7
8
9
10
11
12
use std::collections::HashSet;

impl Solution {
    pub fn intersection(nums1: Vec<i32>, nums2: Vec<i32>) -> Vec<i32> {
        nums1
            .into_iter()
            .collect::<HashSet<_>>()
            .intersection(&nums2.into_iter().collect::<HashSet<_>>())
            .copied()
            .collect()
    }
}

350. 两个数组的交集 II

给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。

示例 1：

1
2
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]

示例 2:

1
2
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]

提示：

  • 1 <= nums1.length, nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 1000

进阶：

  • 如果给定的数组已经排好序呢？你将如何优化你的算法？
  • 如果 nums1 的大小比 nums2 小，哪种方法更优？
  • 如果 nums2 的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？

💡 思路：HashMap：记录交集，出现次数，使用HashMap

代码（思路一）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
use std::collections::HashMap;

impl Solution {
    pub fn intersect(nums1: Vec<i32>, nums2: Vec<i32>) -> Vec<i32> {
        let mut map = HashMap::new();

        for n in nums1 {
            *map.entry(n).or_insert(0) += 1;
        }

        let mut res = Vec::new();

        for &n in &nums2 {
            if let Some(count) = map.get_mut(&n) {
                if *count > 0 {
                    res.push(n);
                    *count -= 1;
                }
            }
        }

        res
    }
}

进阶问题
问：如果给定的数组已经排好序呢？你将如何优化你的算法？

答：可以使用双指针解决，具体实现见下面的双指针写法。这种方法可以将空间复杂度优化至 O(1)。

问：如果 nums1 的大小比 nums2 小，哪种方法更优？

答：在哈希表解法中，将较小的数组转换为哈希表更为高效，这样可以将空间复杂度控制在 O(min(n,m))。

问：如果 nums2 的元素存储在磁盘上，内存有限且无法一次性加载所有元素到内存中，该怎么处理？

答：可以使用小型缓冲区（buffer）边读取边处理数据。这种情况类似于将 nums2 视为数据流（Stream）来处理。我们当前的一次遍历方案已经满足这个要求。

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
impl Solution {
    pub fn intersect(mut nums1: Vec<i32>, mut nums2: Vec<i32>) -> Vec<i32> {
        // 如果保证 nums1 和 nums2 是有序的，排序可以去掉
        nums1.sort_unstable();
        nums2.sort_unstable();

        let mut ans = vec![];
        let mut i = 0;
        let mut j = 0;
        while i < nums1.len() && j < nums2.len() {
            let x = nums1[i];
            let y = nums2[j];
            if x < y {
                i += 1;
            } else if x > y {
                j += 1;
            } else {
                ans.push(x);
                i += 1;
                j += 1;
            }
        }
        ans
    }
}

202. 快乐数

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

  • 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
  • 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
  • 如果这个过程 结果为 1，那么这个数就是快乐数。

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

示例 1：

1
2
3
4
5
6
7
输入：n = 19
输出：true
解释：
1² + 9² = 82
8² + 2² = 68
6² + 8² = 100
1² + 0² + 0² = 1

示例 2：

1
2
输入：n = 2
输出：false

提示：

  • 1 <= n <= 231^-1

💡 思路：

  1. 写一个函数用于计算每个位置上数字平方和
  2. 不断计算数字的平方和，直到结果为 1 或者出现重复数字
  3. 如果最终得到 1 则返回 true，否则 false

代码：

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
use std::collections::HashSet;

impl Solution {
    pub fn is_happy(n: i32) -> bool {
        let mut seen = HashSet::new();
        let mut num = n;
    
        while num != 1 && !seen.contains(&num) {
            seen.insert(num);
            num = Self::sum_of_squares(num);
        }
    
        num == 1
    }

    fn sum_of_squares(mut n: i32) -> i32 {
        let mut sum = 0;
        while n > 0 {
            let digit = n % 10;
            sum += digit * digit;
            n /= 10;
        }
        sum
    }
}

1. 两数之和

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

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

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

示例 1：

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

示例 2：

1
2
输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

1
2
输入：nums = [3,3], target = 6
输出：[0,1]

提示：

  • 2 <= nums.length <= 10^4
  • -10^9 <= nums[i] <= 10^9
  • -10^9 <= target <= 10^9
  • 只会存在一个有效答案

进阶：你可以想出一个时间复杂度小于 O(n²) 的算法吗？

💡 思路：

  1. 需要一个集合来存放我们遍历过的元素，然后在遍历数组的时候去询问这个集合，某元素是否遍历过，也就是某元素是否出现在这个集合。 ⇒ 哈希法
  2. 使用HashMap存储遍历过的元素
  3. 判断需要的元素是否出现在HashMap中

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
use std::collections::HashMap;

impl Solution {
    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
        let mut h = HashMap::new();
        for (i, &num) in nums.iter().enumerate() {
            if let Some(&j) = h.get(&(target - num)) {
                return vec![j as i32, i as i32];
            }

            h.insert(num, i);
        }

        unreachable!();// 不可到达
    }
}

454. 四数相加 II

给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：

  • 0 <= i, j, k, l < n
  • nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

示例 1：

1
2
3
4
5
6
输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出：2
解释：
两个元组如下：
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

示例 2：

1
2
输入：nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
输出：1

提示：

  • n == nums1.length
  • n == nums2.length
  • n == nums3.length
  • n == nums4.length
  • 1 <= n <= 200
  • 2^28 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 2^28

💡 思路：将题目简化成两数之和，先将前两个数组求和，在后两个数组中查找

代码（思路一）：

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
use std::collections::HashMap;

impl Solution {
    pub fn four_sum_count(nums1: Vec<i32>, nums2: Vec<i32>, nums3: Vec<i32>, nums4: Vec<i32>) -> i32 {
        // 创建哈希表存储前两个数组的和及其出现次数
        let mut sum_counts = HashMap::new();
        
        // 计算nums1和nums2所有可能的和及其出现次数
        for &a in &nums1 {
            for &b in &nums2 {
                *sum_counts.entry(a + b).or_insert(0) += 1;
            }
        }

        let mut count = 0;
        
        // 检查nums3和nums4的和的相反数是否在哈希表中
        for &c in &nums3 {
            for &d in &nums4 {
                let complement = -(c + d);
                count += sum_counts.get(&complement).unwrap_or(&0);
            }
        }

        count
    }
}

383. 赎金信

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

示例 1：

1
2
输入：ransomNote = "a", magazine = "b"
输出：false

示例 2：

1
2
输入：ransomNote = "aa", magazine = "ab"
输出：false

示例 3：

1
2
输入：ransomNote = "aa", magazine = "aab"
输出：true

提示：

  • 1 <= ransomNote.length, magazine.length <= 105
  • ransomNote 和 magazine 由小写英文字母组成

💡 思路：

  1. 题意可理解为记录每个字符出现的次数，判断次数是否足够 ⇒ 哈希表 HashMap
  2. 提示 字符串均为小写英文字母 ⇒ 数组代替HashMap

代码（思路一）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
use std::collections::HashMap;

impl Solution {
    pub fn can_construct(ransom_note: String, magazine: String) -> bool {
        let mut count = HashMap::new();

        for m in magazine.chars() {
            *count.entry(m).or_insert(0) += 1;
        }

        for r in ransom_note.chars() {
            if let Some(ele) = count.get_mut(&r) {
                *ele -= 1;
                if *ele < 0 {
                    return false;
                }
            }else {
                return false;
            }
        }

        true
    }
}

代码（数组优化）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
impl Solution {
    pub fn can_construct(ransom_note: String, magazine: String) -> bool {
        let mut count = [0; 26];

        for m in magazine.bytes() {
            count[(m - b'a') as usize] += 1;
        }

        for r in ransom_note.bytes() {
            let x = (r - b'a') as usize;
            count[x] -= 1;
            if count [x] < 0 {
                return false;
            }
        }

        true
    }
}

15. 三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

1
2
3
4
5
6
7
8
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：

1
2
3
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：

1
2
3
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

提示：

  • 3 <= nums.length <= 3000
  • -10^5 <= nums[i] <= 10^5

💡 思路：排序 + 双指针法
这是解决三数之和问题的经典方法，时间复杂度为 O(n²)。
主要步骤：

  1. 首先对数组进行排序
  2. 遍历数组，将当前元素作为第一个数
  3. 使用双指针法在当前元素后面的子数组中寻找另外两个数
  4. 跳过重复元素以避免重复解

代码（思路一）：

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
impl Solution {
    pub fn three_sum(nums: Vec<i32>) -> Vec<Vec<i32>> {
        let mut nums = nums;
        let n = nums.len();
        if n < 3 {
            return vec![];
        }
    
        nums.sort_unstable();// 排序
        let mut result = Vec::with_capacity(n / 3);

				// 寻找 a + b + c = 0, 排序后 a < b < c
        for i in 0..n - 2 {
            if nums[i] > 0 {
                break; // a > 0 不可能有 a + b + c = 0 -> break
            }

            if i > 0 && nums[i] == nums[i-1] {
                continue;// 如果i右移时发现和前一个相等 continue -> 去重
            }

            let target = -nums[i];// left + right
            let mut left = i + 1;
            let mut right = n - 1;

            while left < right {
                let sum = nums[left] + nums[right];

                match sum.cmp(&target) {
                    std::cmp::Ordering::Equal => {// 找到目标
                        result.push(vec![nums[i], nums[left], nums[right]]);

												// 去重
                        let left_val = nums[left];
                        while left < right && nums[left] == left_val {
                            left += 1;
                        }
												// 去重
												let right_val = nums[right];
                        while left < right && nums[right] == right_val {
                            right -= 1;
                        }
                    },
                    std::cmp::Ordering::Less => {
                        left += 1;
                    },
                    std::cmp::Ordering::Greater => {
                        right -= 1;
                    }
                }
            }
        }

        result
    }
}

优化版：

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
impl Solution {
    pub fn three_sum(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
        if nums.len() < 3 {
            return vec![];
        }
        
        nums.sort_unstable();
        let n = nums.len();
        let mut ans = Vec::with_capacity(n / 3);
        
        for i in 0..(n-2) {
            if i > 0 && nums[i] == nums[i-1] {
                continue;
            }
            
            if nums[i] + nums[n-2] + nums[n-1] < 0 {
                continue;
            }
            if nums[i] + nums[i+1] + nums[i+2] > 0 {
                break;
            }
            
            let mut j = i+1;
            let mut k = n-1;
            
            while j < k {
                let sum = nums[i] + nums[j] + nums[k];
                
                if sum > 0 {
                    k -= 1;
                } else if sum < 0 {
                    j += 1;
                } else {
                    ans.push(vec![nums[i], nums[j], nums[k]]);
                    
                    // 重复元素跳过
                    let current_j = nums[j];
                    while j < k && nums[j] == current_j {
                        j += 1;
                    }
                    
                    let current_k = nums[k];
                    while j < k && nums[k] == current_k {
                        k -= 1;
                    }
                }
            }
        }
        
        ans
    }
}

18. 四数之和

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

  • 0 <= a, b, c, d < n
  • a、b、c 和 d 互不相同
  • nums[a] + nums[b] + nums[c] + nums[d] == target

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

示例 1：

1
2
输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]

示例 2：

1
2
输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

提示：

  • 1 <= nums.length <= 200
  • -10^9 <= nums[i] <= 10^9
  • -10^9 <= target <= 10^9

💡 思路：同三数之和，三数之和是固定一个数，用双指针寻找符合条件的数，四数之和可以再加层for循环，固定两个数，再用双指针寻找符合条件的数

代码：

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
use std::cmp::Ordering;

impl Solution {
    pub fn four_sum(mut nums: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
        if nums.len() < 4 {
            return vec![];
        }

        nums.sort_unstable();
        let n = nums.len();
        let target = target as i64;  // 转换为i64防止溢出
        let mut ans = Vec::new();

        for i in 0..(n - 3) {
            // 剪枝
            if (nums[i] as i64 + nums[n-3] as i64 + nums[n-2] as i64 + nums[n-1] as i64) < target {
                continue;
            }
            if (nums[i] as i64 + nums[i+1] as i64 + nums[i+2] as i64 + nums[i+3] as i64) > target {
                break;
            }
            if i > 0 && nums[i] == nums[i-1] {
                continue;
            }
            
            for j in (i+1)..(n-2) {
                // 剪枝
                if (nums[i] as i64 + nums[j] as i64 + nums[n-2] as i64 + nums[n-1] as i64) < target {
                    continue;
                }
                if (nums[i] as i64 + nums[j] as i64 + nums[j+1] as i64 + nums[j+2] as i64) > target {
                    break;
                }
                if j > i+1 && nums[j] == nums[j-1] {
                    continue;
                }

                let mut left = j + 1;
                let mut right = n - 1;

                while left < right {
                    let sum = nums[i] as i64 + nums[j] as i64 + nums[left] as i64 + nums[right] as i64;
                    match sum.cmp(&target) {
                        Ordering::Less => left += 1,
                        Ordering::Greater => right -= 1,
                        Ordering::Equal => {
                            ans.push(vec![nums[i], nums[j], nums[left], nums[right]]);
                            while left < right && nums[left] == nums[left+1] {
                                left += 1;
                            }
                            while left < right && nums[right] == nums[right-1] {
                                right -= 1;
                            }
                            left += 1;
                            right -= 1;
                        }
                    }
                }
            }
        }

        ans
    }
}

哈希表总结

哈希表的主要用途是快速判断一个元素是否存在于集合中。

要理解哈希表，需要掌握哈希函数和哈希碰撞这两个核心概念。

哈希函数负责将输入的key映射到符号表的对应索引位置。当多个key映射到同一个索引位置时，就会发生哈希碰撞。解决碰撞的常用方法包括拉链法和线性探测法。

哈希表主要有以下三种实现结构：

  • 数组
  • set（集合）
  • map（映射）

比如，在不同场景下选择使用不同的实现都需要仔细考虑。

只有深入理解这些数据结构的底层实现，才能熟练运用，避免写出性能低下的代码。

哈希表经典题目

数组作为哈希表

有些应用场景天然适合使用数组实现哈希表。

在242.有效的字母异位词中，我们讨论了数组作为简单哈希表的应用，但要注意数组大小的限制。

对于只包含小写字母的题目，使用数组实现哈希表最为合适。

同样在383.赎金信中，题目限定只有小写字母，这就暗示我们可以使用数组。

这道题与242.有效的字母异位词类似，但有一个关键区别：字母异位词要求两个字符串能相互组成，而赎金信只需要判断字符串a能否组成字符串b。

有人可能会问：为什么不直接用map呢？

虽然这些题目用map也能解决，但map需要维护红黑树或哈希表，还要进行哈希运算，空间开销更大。相比之下，数组实现更简单高效！

set作为哈希表

在349. 两个数组的交集中，我们展示了什么情况下需要从数组转向使用set。

当题目不限制数值范围时，数组就不适合用作哈希表了。

这主要有两个原因：

  • 数组大小受系统栈空间限制（注意，这里说的不是数据结构中的栈）。
  • 当哈希值分布稀疏且跨度很大时，用数组会造成大量空间浪费。

这种情况下，使用set来实现映射更为合适。

map作为哈希表

在1.两数之和这道题中，map展现了它的优势。

让我们先看看数组和set在哈希实现上的局限性：

  • 数组大小受限，且在元素少而哈希值大时会浪费空间。
  • set只能存储单个键值，而两数之和需要同时记录数值和其下标位置。

map作为key, value结构，可以用key存储数值，value存储下标，非常适合这道题。

在454.四数相加中我们发现，需要使用哈希的场景往往都能见到map的身影。

这道题乍看与18. 四数之和和15.三数之和相似，但实际差异很大！

最大的区别在于：本题处理四个独立数组，只需找到A[i] + B[j] + C[k] + D[l] = 0的组合，无需考虑重复问题。而18. 四数之和和15.三数之和需要在同一个数组中寻找和为0的组合，难度更大。

解决了两数之和后，很多人会想用哈希法解决三数之和和四数之和。

虽然理论上可行，但实际操作中需要处理重复问题，导致代码效率低下。这两题还是建议使用双指针解决。