数据结构与算法之 LeetCode 中等题攻略：双指针 + 哈希表组合
在 LeetCode 这样的编程竞赛平台中，中等难度的题目往往需要我们运用多种数据结构和算法技巧。其中，双指针和哈希表是两个非常实用的工具，它们可以有效地解决许多中等难度的题目。本文将围绕这两个主题，结合具体的 LeetCode 题目，进行深入探讨。
双指针
双指针是一种常见的算法技巧，它利用两个指针在数组或链表上移动，从而解决一些特定的问题。双指针通常有以下几种类型：
1. 快慢指针：一个指针每次移动一个单位，另一个指针每次移动两个单位。当快指针到达数组或链表的末尾时，慢指针的位置即为所求。
2. 左右指针：两个指针分别指向数组的两端，通过移动两个指针来寻找满足条件的子数组或子链表。
3. 窗口指针：两个指针定义了一个窗口，窗口的大小可以动态调整，用于解决滑动窗口问题。
题目示例：两数之和
题目描述：给定一个整数数组和一个目标值，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
python
def twoSum(nums, target):
hash_map = {}
for i, num in enumerate(nums):
complement = target - num
if complement in hash_map:
return [hash_map[complement], i]
hash_map[num] = i
return []
在这个例子中，我们使用了哈希表来存储每个数字及其索引，然后通过遍历数组来寻找和为目标值的两个数字。
哈希表
哈希表是一种基于散列原理的数据结构，它可以快速地插入、删除和查找元素。在解决 LeetCode 中等难度的题目时，哈希表可以用来：
1. 去重：快速判断一个元素是否已经存在于集合中。
2. 查找：通过键值对快速查找元素。
3. 计数：统计每个元素出现的次数。
题目示例：有效的字母异位词
题目描述：给定两个字符串 s 和 t ，编写一个函数来检查 t 是否是 s 的字母异位词。
python
def isAnagram(s, t):
if len(s) != len(t):
return False
char_count = {}
for char in s:
char_count[char] = char_count.get(char, 0) + 1
for char in t:
if char not in char_count:
return False
char_count[char] -= 1
if char_count[char] < 0:
return False
return True
在这个例子中，我们使用了哈希表来统计字符串中每个字符的出现次数，然后通过比较两个字符串的字符计数来判断它们是否为字母异位词。
双指针 + 哈希表组合
在某些题目中，我们可以将双指针和哈希表结合起来使用，以解决更复杂的问题。
题目示例：三数之和
题目描述：给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
python
def threeSum(nums):
nums.sort()
result = []
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 < 0:
left += 1
elif total > 0:
right -= 1
else:
result.append([nums[i], nums[left], nums[right]])
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 result
在这个例子中，我们首先对数组进行排序，然后使用双指针来寻找满足条件的三元组。为了防止重复的三元组出现，我们在找到满足条件的三元组后，分别移动左右指针，并跳过相同的元素。
总结
双指针和哈希表是解决 LeetCode 中等难度题目的重要工具。通过结合这两个技巧，我们可以解决许多复杂的问题。在解题过程中，我们需要灵活运用这些技巧，并注意代码的优化和效率。希望本文能帮助你更好地掌握这些技巧，在 LeetCode 的征途上取得更好的成绩。
Comments NOTHING