【算法刷题系列】第6天 242. 有效的字母异位词, 349. 两个数组的交集, 202. 快乐数, 1. 两数之和

calendar Aug 22, 2024 · 3 min read · algorithm 中文  ·
Share on: linkedin copy

Overview

学习内容

学习文档：

哈希表理论基础

收获总结

  1. Go中的rune类型: 在Go语言中，rune是一种别名类型，它表示一个Unicode码点，即一个整数，通常用于表示字符。Go的字符串是以字节数组的形式存储的，因此在处理多字节字符（如汉字、表情符号等）时，直接使用索引访问可能会得到不完整的字符。rune类型解决了这个问题，它能够正确处理和表示多字节的Unicode字符。这对于处理包含非ASCII字符的字符串时非常重要，尤其在国际化或多语言支持的应用中。通过这次学习，我们掌握了如何使用rune遍历字符串，确保对每个字符进行准确的操作。

  2. 数组作为简单高效的哈希表: 在解决某些特定范围的哈希问题时，数组可以作为一种极为简单和高效的哈希表实现方式。特别是在字符计数和映射问题中，如果字符集固定（例如，字母a到z），我们可以使用一个固定长度的整数数组（如[26]int）来记录每个字符的出现次数。数组的索引直接对应字符的ASCII值减去偏移量，这使得字符查找和更新操作都可以在常数时间内完成。学习这部分内容让我们理解了如何在时间复杂度和空间复杂度上进行权衡，选择最合适的数据结构。

  3. Go中使用map实现set: 在Go语言中，集合(set)这一数据结构并没有直接实现，但我们可以通过map来间接实现。使用map[T]struct{}这种方式来模拟集合，其中T是元素类型，struct{}是一种不占用内存的零大小结构体。通过map键的唯一性，保证集合中的元素不重复，同时由于值类型为空结构体，节省了内存空间。我们还学习了如何利用delete函数从map中删除元素，进而动态地管理集合内容。这种技巧在需要高效去重和查找操作的场景中非常有用。

  4. Go中struct{}{}占用空间最小: 在Go语言中，struct{}{}是一个空的结构体类型，占用空间为零。在使用map实现集合时，我们可以将map的值类型定义为struct{}{}，这样可以在实现集合功能的同时，极大地节省内存空间。与其他语言的集合实现相比，这种方式更为轻量级，适合内存受限的场景。通过这种学习，我们进一步理解了Go语言在性能优化方面的设计思想，以及如何在日常编程中应用这些知识提高程序的效率。

  5. 两数之和的双指针与哈希表解法: 对于两数之和问题，如果数组是有序的，我们可以利用双指针（也称为对撞指针）策略，从数组两端同时向中间移动，根据当前和与目标值的比较结果决定指针的移动方向，从而在O(n)时间复杂度内找到解。如果数组是无序的，则可以使用哈希表来记录已遍历过的数值及其索引。在遍历数组时，通过查找哈希表，快速判断是否存在与当前元素互补的数值，并在常数时间内找到目标组合。这些方法各有优劣，双指针法简单直观但只能用于有序数组，而哈希表法适用于无序数组且查找效率更高。通过学习这两种解法，我们理解了不同场景下算法选择的依据。

  6. 扩展知识: 在这次学习中，还扩展了关于哈希表、双指针法在不同算法问题中的广泛应用。深入理解了哈希表在解决查找问题中的效率优势，以及双指针在排序数组中优化搜索过程的应用场景。这些知识不仅在理论层面增强了我们的算法理解，也为我们实际解决编程问题提供了多种思路和工具。

题目解析

题目1：242. 有效的字母异位词

  • 题目描述: 给定两个字符串 s 和 t，编写一个函数来判断 t 是否是 s 的字母异位词。字母异位词是指由相同的字母组成，但排列顺序不同的字符串。注意，字符串中的字母全部为小写字母。

  • 示例:

    1输入: s = "anagram", t = "nagaram"
2输出: true
3
4输入: s = "rat", t = "car"
5输出: false

  • 解法总结: 该题目要求判断两个字符串是否为字母异位词，核心在于统计两个字符串中各字符的出现次数。如果两个字符串中各字符出现的次数完全相同，那么这两个字符串就是字母异位词。解法采用了固定长度的整数数组来记录字符的频次，其中每个字符的频次通过其ASCII码的偏移计算得出。在遍历第一个字符串时，对应字符的计数器加一；在遍历第二个字符串时，对应字符的计数器减一。最后，如果数组中的所有值都为零，则说明两个字符串是字母异位词。这个方法利用了数组的高效查找特性，使得整个过程的时间复杂度保持在O(n)。

     1func isAnagram(s string, t string) bool {
 2	var tmp [26]int
 3	// 1. 映射s到数组+1(数组是简单高效的哈希表)
 4	for _, c := range s {
 5		tmp[c-rune('a')]++
 6	}
 7	// 2. 映射t到数组-1
 8	for _, c := range t {
 9		tmp[c-rune('a')]--
10	}
11
12	// 3. 检查是否有元素不为0
13	for _, c := range tmp {
14		if c != 0 {
15			return false
16		}
17	}
18	return true
19}

  • 时间复杂度: O(n)，其中n是字符串的长度。算法主要耗时在两次遍历字符串上，每次遍历的时间复杂度均为O(n)。

  • 空间复杂度: O(1)。由于使用了固定大小的数组来存储字符频次，无论字符串的长度如何变化，空间复杂度始终保持常数。

题目2：349. 两个数组的交集

  • 题目描述: 给定两个数组，编写一个函数来计算它们的交集。返回结果中的每个元素应是唯一的，结果可以是任意顺序。

  • 示例:

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

  • 解法总结: 该题目的目标是找出两个数组中的公共元素，并确保结果中的元素不重复。通过使用两个map结构，一个用于存储第一个数组中的元素，另一个用于存储交集结果。首先，将第一个数组中的所有元素存入一个map中，以去重。然后，遍历第二个数组，检查每个元素是否存在于第一个数组的map中，如果存在，则将该元素添加到结果集并从map中删除，以确保结果集中元素的唯一性。这种方法利用了哈希表的快速查找特性，能够高效地找出两个数组的交集。

     1func intersection(nums1 []int, nums2 []int) []int {
 2	nums1Map := map[int]struct{}{}
 3	result := []int{}
 4
 5	// 1. 将nums1编入map,并且去重
 6	for _, v := range nums1 {
 7		if _, ok := nums1Map[v]; !ok {
 8			nums1Map[v] = struct{}{}
 9		}
10	}
11
12	// 2. 循环nums2，如果nums1有就放入结果集
13	for _, v := range nums2 {
14		if _, ok := nums1Map[v]; ok {
15			result = append(result, v)
16            delete(nums1Map, v)
17		}
18	}
19
20	return result
21
22}

  • 时间复杂度: O(n + m)，其中n和m分别是两个数组的长度。时间复杂度主要耗费在两个数组的遍历和哈希表的查找操作上。

  • 空间复杂度: O(min(n, m))。空间复杂度主要由存储第一个数组的map以及结果集map决定，取决于两个数组中较小的那个。

题目3：202. 快乐数

  • 题目描述: 编写一个算法来判断一个数n是否是快乐数。快乐数定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程，直到这个数变为1，或是无限循环但始终变不到1。如果可以变为1，则这个数是快乐数。

  • 示例:

    1输入: 19
2输出: true
3解释: 
41² + 9² = 82
58² + 2² = 68
66² + 8² = 100
71² + 0² + 0² = 1

  • 解法总结: 该题目通过不断迭代计算数字的平方和，判断其是否最终收敛到1。为了防止进入无限循环，使用一个map来记录每次迭代后的数字，如果某个数字已经出现过，则表示出现了循环，当前数字不可能是快乐数。具体实现上，首先定义一个辅助函数happyNum来计算平方和，然后在主函数中进行迭代判断，直到数字变为1（返回true）或者出现循环（返回false）。

     1func isHappy(n int) bool {
 2	resultMap := map[int]struct{}{}
 3	// 1. 无限循环计算快乐数
 4	for {
 5		// 2. 计算快乐数
 6		n = happyNum(n)
 7		// 3. 如果快乐数等于1，直接返回true
 8		if n == 1 {
 9			return true
10		}
11
12		// 4. 如果相同的快乐数出现了两次，返回false
13		if _, ok := resultMap[n]; ok {
14			return false
15		}
16		resultMap[n] = struct{}{}
17	}
18}
19
20func happyNum(n int) int {
21	sum := 0
22	// 只适合两位数的
23	for n > 0 {
24		sum += (n % 10) * (n % 10)
25		n = n / 10
26	}
27
28	return sum
29}

  • 时间复杂度: O(logn)。每次迭代中数字的位数减少，最终将收敛到1或出现循环。由于数字的位数与它的对数成正比，因此时间复杂度是O(logn)。

  • 空间复杂度: O(logn)。用于记录中间结果的哈希表最多存储数字的平方和的位数，空间复杂度为O(logn)。

题目4：1. 两数之和

  • 题目描述: 给定一个整数数组nums和一个目标值target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

  • 示例:

    1输入: nums = [2,7,11,15], target = 9
2输出: [0,1]
3解释: 因为 nums[0] + nums[1] = 2 + 7 = 9

  • 解法总结: 对于这道题目，可以采用两种解法：双指针法和哈希表法。如果数组是有序的，可以使用双指针法，通过从两端向中间移动指针，根据当前和与目标值的关系来调整指针，直到找到两个数之和等于目标值的位置。这种方法的时间复杂度为O(n)。如果数组是无序的，可以使用哈希表法。遍历数组的同时，将每个元素及其对应的索引存入哈希表。在遍历过程中，检查哈希表中是否存在目标值与当前元素的差值，如果存在，说明找到了两个数之和等于目标值的位置。这种方法的时间复杂度为O(n)，但空间复杂度也为O(n)。 双指针版本

     1func twoSum(nums []int, target int) []int {
 2	// 1. 定义对撞双指针
 3	// 2. 暴力
 4	for i := 0; i < len(nums); i++ {
 5		for j := i + 1; j < len(nums); j++ {
 6			sum := nums[i] + nums[j]
 7			if sum == target {
 8				return []int{i, j}
 9			}
10		}
11	}
12
13	return []int{}
14}

    哈希表版本

     1func twoSum(nums []int, target int) []int {
 2	resultMap := map[int]int{}
 3
 4	for index, v := range nums {
 5		// 将另一半索引到map里面!
 6		if tarIndex, ok := resultMap[target-v]; ok {
 7			return []int{index, tarIndex}
 8		} else {
 9			resultMap[v] = index
10		}
11	}
12	return []int{}
13}

  • 时间复杂度: 双指针法的时间复杂度为O(n)，哈希表法的时间复杂度也为O(n)。

  • 空间复杂度: 双指针法的空间复杂度为O(1)，哈希表法的空间复杂度为O(n)。