【算法刷题系列】第7天 第454题.四数相加II, 383. 赎金信, 第15题. 三数之和，第18题. 四数之和

calendar Aug 23, 2024 · 5 min read · algorithm 中文  ·
Share on: linkedin copy

Overview

学习内容

学习文档：

收获总结

  1. 哈希表的基本应用: 哈希表是一种通过键值对存储数据的数据结构，具有O(1)的平均查找时间复杂度。其优势在于能够快速判断一个元素是否存在于集合中。通过哈希函数将键映射到存储位置，我们可以在常数时间内完成插入、删除和查找操作。这在需要频繁查找或去重的算法问题中非常有用。

  2. 哈希函数的理解与设计: 哈希函数是哈希表的核心，负责将输入（键）映射到特定的存储桶位置。一个好的哈希函数应当能够均匀地分布输入数据，避免哈希碰撞的发生。哈希碰撞是指不同的输入映射到了同一存储桶，这会导致性能下降。常用的哈希函数设计包括除留余数法、乘积法和平方取中法等。

  3. 哈希碰撞及其处理策略: 哈希碰撞是无法完全避免的，因此需要设计合理的碰撞处理策略。常见的方法有链地址法（即使用链表处理同一存储桶中的多个元素）和开放地址法（即在发生碰撞时寻找下一个可用位置存储）。链地址法的优点是简单易实现，且能处理多种数据类型；而开放地址法则可以更好地利用空间，但在负载因子较高时性能下降明显。

  4. 数组作为特殊的哈希表: 在某些特定的算法问题中，我们可以使用数组来模拟哈希表。特别是当键值范围固定且有限时（如小写字母a-z），数组能够提供与哈希表类似的功能，但由于数组的访问速度更快且无哈希碰撞，因此在特定场景下表现更佳。例如，在统计字符频次的题目中，使用固定大小的数组可以大幅提升性能。

  5. set数据结构的应用: 在某些问题中，需要频繁检查某个元素是否已经存在，或需要确保数据不重复。此时，集合（set）是一种理想的数据结构。Go语言中没有原生的set结构，但可以通过map[T]struct{}来模拟实现，其中T是元素类型。由于struct{}{}在Go语言中不占用额外空间，因此这种方法既节省内存，又能够实现集合所需的所有操作（如插入、删除、查找）。

  6. map作为哈希表的高级应用: Go语言中的map不仅可以用来模拟集合，还能够用于更复杂的场景，如计数器、查找表等。在处理组合问题时，map常用于记录不同组合出现的次数，并通过查找实现快速匹配。例如在"四数相加II"问题中，使用两个map分别记录前两组数的和与后两组数的和，从而在O(1)时间内完成匹配，大大提升了算法效率。

  7. 拓展理解：哈希表在实际问题中的应用: 在实际开发中，哈希表广泛应用于缓存（如LRU缓存）、数据库索引、计数器统计等场景。学习哈希表的基础知识并理解其实现细节，能够帮助我们更好地应对这些实际问题。通过这次学习，我们不仅掌握了哈希表的理论知识，还在实践中理解了如何通过优化哈希函数、处理哈希碰撞等方法，提升算法的效率和可靠性。

题目解析

题目1：第454题.四数相加II

  • 题目描述: 给定四个整数数组nums1、nums2、nums3和nums4，统计有多少个四元组(i, j, k, l)使得nums1[i] + nums2[j] + nums3[k] + nums4[l] = 0。为了简化问题，假设所有的四个数组长度相同，且长度不超过500。

  • 示例:

    1输入: nums1 = [1, 2], nums2 = [-2,-1], nums3 = [-1, 2], nums4 = [0, 2]
2输出: 2
3解释: 两个符合条件的四元组为:
4(0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
5(1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

  • 解法总结: 该题目要求我们找到所有满足条件的四元组。直接暴力枚举四个数组中的元素组合会导致O(n^4)的时间复杂度，无法在合理时间内解决问题。因此，利用哈希表的快速查找特性可以将问题转化为两两分组求和。首先，我们遍历nums1和nums2，计算每对元素的和，并将其存储在哈希表中，键为和，值为出现的次数。然后遍历nums3和nums4，计算它们的和并检查哈希表中是否存在该和的相反数，如果存在则说明找到了符合条件的四元组，结果增加该和的出现次数。通过这种方法，时间复杂度降低到了O(n^2)。

     1func fourSumCount(nums1 []int, nums2 []int, nums3 []int, nums4 []int) int {
 2	resultMap := map[int]int{}
 3	result := 0
 4
 5	// 1. 第一部分for循环循环nums1，nums2，之和作为key，value为组合次数
 6	for _, v := range nums1 {
 7		for _, sV := range nums2 {
 8			resultMap[v+sV]++
 9		}
10	}
11
12	// 2. 第二部分for循环直接比对resultMap是否有答案
13	for _, v := range nums3 {
14		for _, sV := range nums4 {
15			if ssV, ok := resultMap[0-(v+sV)]; ok {
16				result += ssV
17			}
18		}
19	}
20	return result
21}

  • 时间复杂度: O(n^2)，其中n是每个数组的长度。我们首先计算两两数组组合的和，这需要O(n^2)的时间，然后在第二部分查找哈希表也需要O(n^2)的时间。

  • 空间复杂度: O(n^2)，用于存储前两组数的和的哈希表。这个哈希表最多存储n^2个不同的和，因此空间复杂度为O(n^2)。

题目2：383. 赎金信

  • 题目描述: 给定一个ransomNote字符串和一个magazine字符串，判断ransomNote能否由magazine里面的字符构成。如果可以，返回true；否则返回false。magazine中的每个字符只能在ransomNote中使用一次。

  • 示例:

    1输入: ransomNote = "a", magazine = "b"
2输出: false
3
4输入: ransomNote = "aa", magazine = "ab"
5输出: false
6
7输入: ransomNote = "aa", magazine = "aab"
8输出: true

  • 解法总结: 这道题的关键在于判断magazine中是否有足够的字符可以构成ransomNote。解法是遍历magazine字符串并统计每个字符的出现次数，然后遍历ransomNote字符串，检查每个字符是否可以在magazine中找到并且次数足够。如果某个字符的数量不够，则直接返回false。如果所有字符都满足条件，则返回true。通过使用一个固定大小的数组来记录字符的出现次数，可以在O(1)时间内完成查找和更新操作，这种方法有效地利用了数组作为特殊哈希表的特性。

     1func canConstruct(ransomNote string, magazine string) bool {
 2	magazineMap := make([]int, 26)
 3
 4	// 1. magazine只能用一次，magazine映射到map，+1
 5	for _, v := range magazine {
 6		magazineMap[v-rune('a')]++
 7	}
 8
 9	// 2. 循环ransomNote进行-1，如果减完了小于0，则返回false；最后返回true
10	for _, v := range ransomNote {
11		magazineMap[v-rune('a')]--
12		if magazineMap[v-rune('a')] < 0 {
13			return false
14		}
15	}
16	return true
17}

  • 时间复杂度: O(n + m)，其中n和m分别是ransomNote和magazine的长度。我们需要分别遍历这两个字符串来统计和检查字符的出现次数。

  • 空间复杂度: O(1)，因为我们使用了一个固定大小的数组（长度为26）来存储字符的频次，不随输入大小变化。

题目3：第15题. 三数之和

  • 题目描述: 给定一个包含n个整数的数组nums，判断nums中是否存在三个元素a，b，c，使得a + b + c = 0。请找出所有和为0且不重复的三元组。

  • 示例:

    1输入: nums = [-1, 0, 1, 2, -1, -4]
2输出: [[-1, 0, 1], [-1, -1, 2]]

  • 解法总结: 该题目要求找出所有和为0的三元组，且不能有重复的三元组。暴力解法会尝试每个三元组合，时间复杂度为O(n^3)，效率低下。为提高效率，可以首先对数组进行排序，然后利用双指针法进行查找：固定一个数作为基准，剩下的两个数通过左右双指针向中间搜索，确保找到的三元组和为零。排序能够帮助我们轻松跳过重复的元素，避免产生重复的结果。最终的时间复杂度为O(n^2)，远优于暴力解法。

    暴力解法: 注意，暴力解法虽然正确，但是会超时；第二种双指针写法更优

     1func threeSum(nums []int) [][]int {
 2	checkMap := map[int]int{}
 3	result := [][]int{}
 4	seenMap := map[string]struct{}{}
 5
 6	// 1. 第一轮循环，从头扫描到尾，把对应的值放checkMap进去，key是0-v，value是index
 7	for index, v := range nums {
 8		checkMap[0-v] = index
 9
10	}
11
12	// 2. 第二轮循环，双指针循环(不重复)，同时需要相加判断checkMap是否有，index是否重合
13	for i := 0; i < len(nums); i++ {
14		for j := i + 1; j < len(nums); j++ {
15			if v, ok := checkMap[nums[i]+nums[j]]; ok {
16				if v != i && v != j {
17					tmp := []int{nums[v], nums[i], nums[j]}
18					sort.Ints(tmp)
19					if _, ok := seenMap[fmt.Sprintf("%d%d%d", tmp[0], tmp[1], tmp[2])]; !ok {
20						result = append(result, tmp)
21						seenMap[fmt.Sprintf("%d%d%d", tmp[0], tmp[1], tmp[2])] = struct{}{}
22					}
23				}
24			}
25		}
26	}
27	return result
28}

    对撞双指针解法

     1import "sort"
 2
 3func threeSum(nums []int) [][]int {
 4	result := [][]int{}
 5
 6	// 0. 排序数组(默认由小到大)，这个是后面对撞双指针的前提
 7	sort.Ints(nums)
 8
 9	// 1. 由于要找三个数，在不重复的情况下，i应该<len-2
10	for i := 0; i < len(nums)-2; i++ {
11		// 2. 并且排序后如果已经>0了都直接跳过
12		if nums[i] > 0 {
13			break
14		}
15
16		// 3. 去重a
17		if i >= 1 && nums[i] == nums[i-1] {
18			continue
19		}
20
21		// 4. 对撞双指针找b和c
22		left := i + 1
23		right := len(nums) - 1
24
25		for left < right {
26			b, c := nums[left], nums[right]
27			if nums[i]+b+c == 0 {
28				tmp := []int{nums[i], b, c}
29				result = append(result, tmp)
30
31				// 去重b
32				for left < right && nums[left] == b {
33					left++
34				}
35				// 去重c
36				for left < right && nums[right] == c {
37					right--
38				}
39			} else if nums[i]+b+c < 0 {
40				left++
41			} else {
42				right--
43			}
44		}
45	}
46	return result
47}

  • 时间复杂度: O(n^2)。排序需要O(n log n)，双指针查找需要O(n^2)。

  • 空间复杂度: O(1)。除了排序所需的空间外，不需要额外的空间来存储数据。

题目4：第18题. 四数之和

  • 题目描述: 给定一个包含n个整数的数组nums和一个目标值target，判断nums中是否存在四个元素a，b，c，d，使得a + b + c + d的和与target相等。请找出所有符合条件且不重复的四元组。

  • 示例:

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

  • 解法总结: 该题目是“三数之和”的扩展版，要求找到四个数的和等于目标值的所有不重复四元组。解法与“三数之和”类似，可以通过排序和双指针法来解决。首先对数组进行排序，然后固定两个数，剩下的两个数通过左右双指针进行搜索，确保找到的四元组和为目标值。为了避免重复解，固定的数以及双指针搜索过程中都需要进行去重处理。最终时间复杂度为O(n^3)，其中n是数组的长度。

    对撞双指针解法

     1import "sort"
 2
 3func fourSum(nums []int, target int) [][]int {
 4	result := [][]int{}
 5	// 双指针解法
 6	// 0. 排序
 7	sort.Ints(nums)
 8
 9	// 1. a+b+c+d 第一个循环a
10	for i := 0; i < len(nums)-3; i++ {
11		// a去重
12		a := nums[i]
13		if i > 0 && a == nums[i-1] {
14			continue
15		}
16
17		// 2. 往后循环b
18		for j := i + 1; j < len(nums)-2; j++ {
19			b := nums[j]
20			if j > i+1 && b == nums[j-1] {
21				continue
22			}
23
24			// 3. 双指针c，d(left, right)
25			left := j + 1
26			right := len(nums) - 1
27
28			for left < right {
29				c := nums[left]
30				d := nums[right]
31				sum := a + b + c + d
32				if sum == target {
33					result = append(result, []int{a, b, c, d})
34					// 如果下一个数字和已经加入result的相同，就直接按照方向跳过
35					for left < right && nums[left] == nums[left+1] {
36						left++
37					}
38					for left < right && nums[right] == nums[right-1] {
39						right--
40					}
41					// 双指针同时移动
42					left++
43					right--
44				} else if sum < target {
45					left++
46				} else {
47					right--
48				}
49			}
50		}
51	}
52	return result
53}

  • 时间复杂度: O(n^3)。排序需要O(n log n)，三层嵌套循环分别是O(n^3)。

  • 空间复杂度: O(1)。除了排序所需的空间外，不需要额外的空间来存储数据。