【代码随想录 | Leetcode | 第十天】哈希表 | 三数之和 | 四数之和

**第十天：哈希表 | 三数之和 | 四数之和**

在前几天的文章中，我们已经学习了如何使用双指针法解决一系列的问题，如两数之和、滑动窗口等。今天我们将继续深入探索另一种常见的算法思想——哈希表。

**什么是哈希表？**

哈希表（Hash Table）是一种数据结构，它通过计算一个值的散列函数来快速定位存储在该数据结构中的值。哈希表通常由两个部分组成：一个数组和一个散列函数。数组用于存储键值对，而散列函数则用于将键转换为索引。

**三数之和**

首先，我们来看一下三数之和的问题：

给定一个整数数组 `nums` 和一个目标整数 `target`，找出三个数字的和等于 `target` 的所有可能组合。

示例：

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

我们可以使用哈希表来解决这个问题。具体来说，我们可以先将 `nums` 中的数字排序，然后遍历数组，计算每个数字与其前两个数字之和是否等于 `target`。

def threeSum(nums):
 nums.sort()
 res = []
 for i in range(len(nums) -2):
 if i >0 and nums[i] == nums[i-1]:
 continue left, right = i +1, len(nums) -1 while left < right:
 total = nums[i] + nums[left] + nums[right]
 if total < target:
 left +=1 elif total > target:
 right -=1 else:
 res.append([nums[i], nums[left], nums[right]])
 # Skip duplicates for left and right pointers while left < right and nums[left] == nums[left +1]:
 left +=1 while left < right and nums[right] == nums[right -1]:
 right -=1 left +=1 right -=1 return res# Test the functionnums = [1,2,3,4]
target =6print(threeSum(nums))

**四数之和**

接下来，我们来看一下四数之和的问题：

给定一个整数数组 `nums` 和一个目标整数 `target`，找出四个数字的和等于 `target` 的所有可能组合。

示例：

* 输入：`nums = [1,2,3,4]`, `target =8`
输出：`[[1,1,2,4], [1,2,2,3]]`

我们可以使用哈希表来解决这个问题。具体来说，我们可以先将 `nums` 中的数字排序，然后遍历数组，计算每个数字与其前三个数字之和是否等于 `target`。

def fourSum(nums):
 nums.sort()
 res = []
 for i in range(len(nums) -3):
 if i >0 and nums[i] == nums[i-1]:
 continue for j in range(i +1, len(nums) -2):
 if j > i +1 and nums[j] == nums[j-1]:
 continue left, right = j +1, len(nums) -1 while left < right:
 total = nums[i] + nums[j] + nums[left] + nums[right]
 if total < target:
 left +=1 elif total > target:
 right -=1 else:
 res.append([nums[i], nums[j], nums[left], nums[right]])
 # Skip duplicates for left and right pointers while left < right and nums[left] == nums[left +1]:
 left +=1 while left < right and nums[right] == nums[right -1]:
 right -=1 left +=1 right -=1 return res# Test the functionnums = [1,2,3,4]
target =8print(fourSum(nums))

**总结**

在本文中，我们学习了如何使用哈希表解决三数之和和四数之和的问题。通过对这些问题的分析和代码示例，我们可以看到哈希表是一种非常有效的数据结构，可以帮助我们快速找到满足特定条件的组合。

**参考资料**

* [LeetCode]( />* [GeeksforGeeks](