算法竞赛三大核心技巧：哈希、双指针与滑动窗口

1. 算法竞赛中的三大核心技巧在算法竞赛和编程面试中哈希、双指针和滑动窗口是解决大量问题的关键技巧。这些方法不仅能显著提升解题效率更是面试官考察候选人算法思维的重要维度。作为力扣LeetCode热题100中的高频考点掌握这三种技巧可以覆盖约30%的中等难度题目。哈希Hash技术通过建立键值映射关系将查找时间复杂度从O(n)降低到O(1)。双指针Two Pointers则通过维护两个指针变量在单次遍历中完成复杂操作。滑动窗口Sliding Window是双指针的进阶应用专门处理子数组/子字符串类问题。实际编程面试中约60%的数组/字符串问题都可以用这三种技巧或其组合解决。特别是在处理满足某条件的最长子串、两数之和、无重复字符的最长子串这类经典问题时这些技巧往往是最优解。2. 哈希技术的深度解析与应用2.1 哈希表的基础实现哈希表的核心在于哈希函数的设计和冲突处理。以C为例标准库提供了unordered_map作为哈希表实现其内部采用开链法处理冲突#include unordered_map std::unordered_mapint, std::string hashMap; hashMap[1] Apple; // 插入操作 O(1) auto it hashMap.find(1); // 查找操作 O(1)Python中的字典本质也是哈希表hash_map {} hash_map[1] Apple # 插入 value hash_map.get(1) # 查找2.2 哈希在算法题中的典型应用**两数之和LeetCode 1**是最经典的哈希应用题。暴力解法需要O(n²)时间而哈希可将复杂度降至O(n)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 []实际应用中的注意事项当需要存储原始索引时应在插入哈希前先检查补数对于对象作为键的情况需确保正确实现了hashCode和equals方法C中单模数哈希要注意模数选择足够大的质数如1e97避免冲突2.3 高级哈希技巧前缀和哈希的组合可以解决子数组和问题。例如LeetCode 560和为K的子数组def subarraySum(nums, k): prefix_sum {0: 1} current_sum 0 count 0 for num in nums: current_sum num count prefix_sum.get(current_sum - k, 0) prefix_sum[current_sum] prefix_sum.get(current_sum, 0) 1 return count这种技巧的时间复杂度为O(n)相比暴力解的O(n²)有显著提升。关键在于利用哈希存储前缀和的出现次数通过current_sum - k的计算快速定位满足条件的子数组。3. 双指针技术的精妙运用3.1 同向双指针**移除元素LeetCode 27**展示了同向双指针的典型用法def removeElement(nums, val): slow 0 for fast in range(len(nums)): if nums[fast] ! val: nums[slow] nums[fast] slow 1 return slow这里slow指针跟踪新数组位置fast指针遍历原数组。时间复杂度O(n)空间复杂度O(1)比创建新数组更高效。3.2 相向双指针**盛最多水的容器LeetCode 11**需要从两端向中间移动指针def maxArea(height): left, right 0, len(height) - 1 max_area 0 while left right: area min(height[left], height[right]) * (right - left) max_area max(max_area, area) if height[left] height[right]: left 1 else: right - 1 return max_area这种策略每次移动较矮的一边确保不会错过更大容量的可能性时间复杂度仍为O(n)。3.3 双指针的特殊变种快慢指针用于检测循环LeetCode 141或找到中点LeetCode 876def hasCycle(head): slow fast head while fast and fast.next: slow slow.next fast fast.next.next if slow fast: return True return False快指针以两倍速度移动当它们相遇时说明存在环。这种技巧无需额外空间是检测链表环的最优解。4. 滑动窗口的高效实现4.1 固定大小窗口**滑动窗口最大值LeetCode 239**需要维护一个递减的双端队列def maxSlidingWindow(nums, k): from collections import deque q deque() result [] for i, num in enumerate(nums): while q and nums[q[-1]] num: q.pop() q.append(i) if q[0] i - k: q.popleft() if i k - 1: result.append(nums[q[0]]) return result这种解法时间复杂度为O(n)每个元素最多进出队列一次。关键在于队列中存储的是可能成为窗口最大值的候选索引。4.2 可变大小窗口**无重复字符的最长子串LeetCode 3**需要动态调整窗口大小def lengthOfLongestSubstring(s): char_map {} left max_len 0 for right, char in enumerate(s): if char in char_map and char_map[char] left: left char_map[char] 1 char_map[char] right max_len max(max_len, right - left 1) return max_len这里哈希表记录字符最后出现的位置当发现重复时快速移动左指针。算法时间复杂度O(n)空间复杂度O(min(m,n))其中m是字符集大小。4.3 滑动窗口的优化技巧**最小覆盖子串LeetCode 76**需要结合哈希和滑动窗口def minWindow(s, t): from collections import defaultdict target defaultdict(int) for c in t: target[c] 1 left formed 0 min_len float(inf) result current defaultdict(int) for right in range(len(s)): char s[right] if char in target: current[char] 1 if current[char] target[char]: formed 1 while formed len(target): if right - left 1 min_len: min_len right - left 1 result s[left:right1] left_char s[left] if left_char in target: current[left_char] - 1 if current[left_char] target[left_char]: formed - 1 left 1 return result这个解法通过formed变量跟踪已满足条件的字符数避免每次检查全部字符。时间复杂度O(|S||T|)其中|S|和|T|分别是字符串s和t的长度。5. 组合技巧的高级应用5.1 哈希滑动窗口解决复杂问题**字符串的排列LeetCode 567**需要检查s2是否包含s1的排列def checkInclusion(s1, s2): from collections import defaultdict target defaultdict(int) window defaultdict(int) for c in s1: target[c] 1 left valid 0 for right in range(len(s2)): char s2[right] if char in target: window[char] 1 if window[char] target[char]: valid 1 while right - left 1 len(s1): if valid len(target): return True left_char s2[left] if left_char in target: if window[left_char] target[left_char]: valid - 1 window[left_char] - 1 left 1 return False这种解法通过valid计数避免每次比较整个哈希表将时间复杂度控制在O(n)。5.2 双指针哈希的混合使用**四数之和LeetCode 18**可以结合双指针和哈希def fourSum(nums, target): nums.sort() n len(nums) result set() for i in range(n-3): for j in range(i1, n-2): left j 1 right n - 1 while left right: total nums[i] nums[j] nums[left] nums[right] if total target: result.add((nums[i], nums[j], nums[left], nums[right])) left 1 right - 1 elif total target: left 1 else: right - 1 return list(result)虽然主要使用双指针但结合哈希可以进一步优化去重过程。时间复杂度为O(n³)但通过提前排序和剪枝可以显著提升实际性能。5.3 多技巧组合的边界处理在实际编码中组合使用这些技巧时需要特别注意边界条件哈希表访问不存在的键时的默认值处理双指针移动时的数组越界检查滑动窗口收缩时的条件判断顺序指针移动和哈希表更新的时序关系例如在实现至多包含K个不同字符的最长子串时需要同时维护哈希计数和窗口边界def lengthOfLongestSubstringKDistinct(s, k): from collections import defaultdict count defaultdict(int) left max_len 0 for right in range(len(s)): count[s[right]] 1 while len(count) k: count[s[left]] - 1 if count[s[left]] 0: del count[s[left]] left 1 max_len max(max_len, right - left 1) return max_len这种实现确保在窗口内字符种类超过K时能正确收缩同时保持线性时间复杂度。