LeetCode 热题 HOT100（二）：双指针进阶与滑动窗口（Go 实现）

个人主页会编程的土豆欢迎来访作者简介后端学习者❄️个人专栏数据结构与算法数据库leetcode✨那些你一个人走过的夜路终将化作照亮未来的光本文覆盖力扣「热题 100」学习计划第 610 题全部使用Go实现。可与上一篇哈希表与双指针入门对照阅读。题单入口LeetCode 热题 10015. 三数之和难度中等标签数组、双指针、排序题目链接15. 三数之和题目描述给你一个整数数组nums判断是否存在三元组[nums[i], nums[j], nums[k]]满足i ! j、i ! k且j ! k并且nums[i] nums[j] nums[k] 0。请你返回所有和为0且不重复的三元组。示例输入nums [-1,0,1,2,-1,-4] 输出[[-1,-1,2],[-1,0,1]]思路分析先排序方便去重和双指针移动枚举第一个数nums[i]在右侧用双指针找两数之和等于-nums[i]遇到相同元素跳过避免重复三元组注意若nums[i] 0后面全为正可直接结束。Go 代码func threeSum(nums []int) [][]int { sort.Ints(nums) n : len(nums) res : make([][]int, 0) for i : 0; i n-2; i { if nums[i] 0 { break } if i 0 nums[i] nums[i-1] { continue } left, right : i1, n-1 for left right { sum : nums[i] nums[left] nums[right] if sum 0 { res append(res, []int{nums[i], nums[left], nums[right]}) for left right nums[left] nums[left1] { left } for left right nums[right] nums[right-1] { right-- } left right-- } else if sum 0 { left } else { right-- } } } return res }记得导入import sort复杂度时间复杂度O(n²)空间复杂度O(1)不计返回结果42. 接雨水难度困难标签栈、数组、双指针、动态规划、单调栈题目链接42. 接雨水题目描述给定n个非负整数表示每个宽度为 1 的柱子的高度图计算按此排列的柱子下雨之后能接多少雨水。示例输入height [0,1,0,2,1,0,1,3,2,1,2,1] 输出6思路分析双指针写法维护leftMax/rightMax当前位置左侧/右侧的最高柱哪边最大值更小就先结算哪边当前能接的水 该侧最大值 - 当前高度指针向中间移动直到相遇理解水位由「较矮一侧的最高柱」决定。Go 代码func trap(height []int) int { left, right : 0, len(height)-1 leftMax, rightMax : 0, 0 water : 0 for left right { if height[left] height[right] { if height[left] leftMax { leftMax height[left] } else { water leftMax - height[left] } left } else { if height[right] rightMax { rightMax height[right] } else { water rightMax - height[right] } right-- } } return water }复杂度时间复杂度O(n)空间复杂度O(1)3. 无重复字符的最长子串难度中等标签哈希表、字符串、滑动窗口题目链接3. 无重复字符的最长子串题目描述给定一个字符串s请你找出其中不含有重复字符的最长子串的长度。示例输入: s abcabcbb 输出: 3 解释: 因为无重复字符的最长子串是 abc所以其长度为 3。思路分析经典滑动窗口右指针不断扩展窗口用哈希表记录字符最后出现下标若右端字符已在窗口内出现左指针跳到该字符上次位置的下一位每步更新最大长度Go 代码func lengthOfLongestSubstring(s string) int { lastIndex : make(map[byte]int) left : 0 maxLen : 0 for right : 0; right len(s); right { ch : s[right] if idx, ok : lastIndex[ch]; ok idx left { left idx 1 } lastIndex[ch] right if right-left1 maxLen { maxLen right - left 1 } } return maxLen }复杂度时间复杂度O(n)空间复杂度O(|Σ|)字符集大小438. 找到字符串中所有字母异位词难度中等标签哈希表、字符串、滑动窗口题目链接438. 找到字符串中所有字母异位词题目描述给定两个字符串s和p找到s中所有p的异位词的子串返回这些子串的起始索引。不考虑答案输出的顺序。示例输入: s cbaebabacd, p abc 输出: [0,6] 解释: 起始索引等于 0 的子串是 cba, 它是 abc 的异位词。 起始索引等于 6 的子串是 bac, 它是 abc 的异位词。思路分析固定长度滑动窗口统计p的字符频次need维护窗口内字符频次window以及「已匹配字符种类数」valid窗口长度等于len(p)时判断是否完全匹配再右移时弹出左端字符字母表只有 26 个小写字母也可用[26]int数组比较。Go 代码func findAnagrams(s string, p string) []int { if len(s) len(p) { return nil } var need, window [26]int for i : 0; i len(p); i { need[p[i]-a] } res : make([]int, 0) left : 0 for right : 0; right len(s); right { window[s[right]-a] if right-left1 len(p) { window[s[left]-a]-- left } if right-left1 len(p) window need { res append(res, left) } } return res }复杂度时间复杂度O(n)n 为s长度空间复杂度O(1)560. 和为 K 的子数组难度中等标签数组、哈希表、前缀和题目链接560. 和为 K 的子数组题目描述给你一个整数数组nums和一个整数k请你统计并返回该数组中和为k的子数组的个数。子数组是数组中元素的连续非空序列。示例输入nums [1,1,1], k 2 输出2思路分析前缀和 哈希表记pre[i]为前i个数之和若存在j使得pre[i] - pre[j] k则(j, i]这一段和为k用哈希表记录「前缀和出现次数」遍历时先查pre - k的次数再把当前pre计入表注意初始要放入0:1表示前缀和为 0 出现过一次空前缀。Go 代码func subarraySum(nums []int, k int) int { count : make(map[int]int) count[0] 1 pre, ans : 0, 0 for _, num : range nums { pre num ans count[pre-k] count[pre] } return ans }复杂度时间复杂度O(n)空间复杂度O(n)小结题目核心技巧时间复杂度三数之和排序 双指针去重O(n²)接雨水左右双指针 左右最高柱O(n)无重复字符的最长子串滑动窗口 哈希表O(n)找到所有字母异位词定长滑动窗口 频次数组O(n)和为 K 的子数组前缀和 哈希表O(n)两篇合集对照序号题目篇目1两数之和第一篇2字母异位词分组第一篇3最长连续序列第一篇4移动零第一篇5盛最多水的容器第一篇6三数之和本文7接雨水本文8无重复字符的最长子串本文9找到所有字母异位词本文10和为 K 的子数组本文到这里Hot100 前 10 题的 Go 题解就齐了。建议每题自己敲一遍再对照思路巩固。如果对你有帮助欢迎点赞收藏后面可以继续写 Hot100 后续专题链表、二叉树、动态规划等