其他重要思想：滑动窗口、双指针、位运算、随机化算法

写在前面在算法设计中除了经典的数据结构和算法模型还有一些精妙的“思想”能让我们以简洁的方式解决问题。它们往往不需要复杂的数据结构只需巧妙地利用指针移动、二进制特性或概率方法就能高效解题。本文带你系统学习四种重要思想滑动窗口在数组/字符串上维护一个动态窗口解决子数组/子串问题双指针利用两个指针从两端或同向遍历减少循环嵌套位运算利用二进制位的特性实现高效判断、状态压缩随机化算法用概率方法近似求解或优化确定性算法每部分均包含一句话记住、核心思想、流程图推荐、代码实现、LeetCode实战附题目链接及解题代码。一、滑动窗口Sliding Window 一句话记住用左右指针维护一个窗口根据条件移动右指针扩大窗口移动左指针缩小窗口。 核心思想滑动窗口适用于求解连续子数组/子串的最优解问题如最长无重复子串、最小覆盖子串。维护两个指针left和right表示窗口的左右边界右指针向右扩展窗口左指针根据条件收缩窗口同时用哈希表或数组记录窗口内的状态。时间复杂度 O(n)。 流程图​​​​​滑动窗口 算法框架图LeetCode官方题解—包含窗口移动的动图演示可直接截图 代码实现最长无重复子串模板function lengthOfLongestSubstring(s) { const map new Map(); let left 0, maxLen 0; for (let right 0; right s.length; right) { const char s[right]; if (map.has(char)) { // 左指针移动到重复字符的下一个位置 left Math.max(left, map.get(char) 1); } map.set(char, right); maxLen Math.max(maxLen, right - left 1); } return maxLen; } LeetCode实战例题1无重复字符的最长子串题目LeetCode 3. 无重复字符的最长子串解题思路维护一个窗口[left, right]用哈希表记录每个字符最后出现的位置。右指针right不断向右移动当遇到重复字符时左指针left移动到该字符上次出现位置的下一个保证窗口内无重复。每次窗口调整后计算当前窗口长度更新答案。时间复杂度 O(n)。解题代码见上方。例题2最小覆盖子串题目LeetCode 76. 最小覆盖子串解题思路用哈希表或数组记录目标串t中每个字符的需求量need。右指针向右扩展遇到need中的字符就减少需求量当need中所有字符需求量 ≤0 时当前窗口已覆盖t。此时尝试收缩左指针尽可能缩小窗口并更新最小覆盖子串的起止位置。当左指针移动导致需求量再次出现 0 时停止收缩继续右移右指针。时间复杂度 O(n)。解题代码var minWindow function(s, t) { const need new Array(128).fill(0); for (const ch of t) need[ch.charCodeAt()]; let left 0, right 0, start 0, minLen Infinity, count t.length; while (right s.length) { const rc s.charCodeAt(right); if (need[rc] 0) count--; need[rc]--; right; while (count 0) { if (right - left minLen) { minLen right - left; start left; } const lc s.charCodeAt(left); need[lc]; if (need[lc] 0) count; left; } } return minLen Infinity ? : s.substr(start, minLen); };二、双指针Two Pointers 一句话记住两个指针同向或相向移动减少循环嵌套将 O(n²) 降为 O(n)。 核心思想双指针常用于有序数组/链表的问题。两种常见模式相向双指针一个在头一个在尾向中间移动如两数之和、回文判断。快慢双指针一个走一步一个走两步用于链表环检测、寻找中点。通过指针移动避免暴力枚举。 流程图​​​​​​​https://oi-wiki.org/misc/two-pointer/ 代码实现两数之和 IIfunction twoSum(numbers, target) { let left 0, right numbers.length - 1; while (left right) { const sum numbers[left] numbers[right]; if (sum target) return [left 1, right 1]; if (sum target) left; else right--; } return []; } LeetCode实战例题1两数之和 II - 输入有序数组题目LeetCode 167. 两数之和 II - 输入有序数组解题思路利用数组有序的性质使用相向双指针。初始化left0rightn-1。计算nums[left]nums[right]若等于目标则返回若小于目标则左指针右移增大和若大于目标则右指针左移减小和。因为数组升序这样移动保证不会遗漏解。时间复杂度 O(n)。解题代码见上方。例题2验证回文串题目LeetCode 125. 验证回文串解题思路先将字符串统一转小写并去除非字母数字字符或直接在比较时跳过非字母数字。使用相向双指针左指针从头开始右指针从尾开始。当左右指针都指向有效字符时比较是否相等若不相等则返回 false若相等则继续向中间移动。直到左指针≥右指针返回 true。时间复杂度 O(n)。解题代码var isPalindrome function(s) { s s.toLowerCase().replace(/[^a-z0-9]/g, ); let left 0, right s.length - 1; while (left right) { if (s[left] ! s[right]) return false; left; right--; } return true; };三、位运算Bit Manipulation 一句话记住利用二进制位操作实现高效判断、状态压缩、快速计算。 核心思想位运算直接在二进制位上操作常用技巧n (n-1)将 n 的最低位的 1 置为 0用于统计二进制中 1 的个数。n (-n)得到 n 的最低位的 1 对应的数值lowbit。x ^ x 0、x ^ 0 x用于找出现奇数次的数。(x i) 1判断第 i 位是否为 1。状态压缩用整数表示集合状态如dp[mask]。 流程图https://oi-wiki.org/math/bit/ 代码实现统计二进制中1的个数function countBits(n) { let count 0; while (n) { n n - 1; count; } return count; } LeetCode实战例题1只出现一次的数字题目LeetCode 136. 只出现一次的数字解题思路利用异或运算的性质a⊕a0a⊕0a且满足交换律和结合律。将所有数字异或起来成对出现的数字会抵消为 0剩下的就是只出现一次的数字。时间复杂度 O(n)空间 O(1)。解题代码var singleNumber function(nums) { let result 0; for (const num of nums) result ^ num; return result; };例题2子集状态压缩题目LeetCode 78. 子集解题思路长度为 n 的数组共有 2ⁿ 个子集可以用 0 到 2ⁿ-1 的整数表示每个子集。整数mask的二进制位中第 i 位为 1 表示选择nums[i]。遍历所有 mask根据二进制位将对应元素加入子集即可得到所有子集。时间复杂度 O(n·2ⁿ)适合 n ≤ 20 的情况。解题代码var subsets function(nums) { const n nums.length; const result []; for (let mask 0; mask (1 n); mask) { const subset []; for (let i 0; i n; i) { if (mask (1 i)) subset.push(nums[i]); } result.push(subset); } return result; };四、随机化算法Randomized Algorithms 一句话记住用随机性换取效率或简化问题接受小概率错误或期望复杂度。 核心思想随机化算法通过引入随机性来简化算法设计常见类型蒙特卡洛算法可能返回错误结果但错误概率可控制如随机化快速排序的随机选主元拉斯维加斯算法总是返回正确结果但运行时间不确定如随机化快排随机化数据结构的应用跳表、布隆过滤器之前哈希查找已介绍 流程图https://oi-wiki.org/misc/random/ 代码实现随机化快速排序的 partitionfunction randomizedPartition(arr, left, right) { const randomIndex left Math.floor(Math.random() * (right - left 1)); [arr[left], arr[randomIndex]] [arr[randomIndex], arr[left]]; const pivot arr[left]; let i left; for (let j left 1; j right; j) { if (arr[j] pivot) { i; [arr[i], arr[j]] [arr[j], arr[i]]; } } [arr[left], arr[i]] [arr[i], arr[left]]; return i; } LeetCode实战例题随机化快速排序非直接考题但可应用题目LeetCode 912. 排序数组用随机化快排实现解题思路快速排序最坏情况发生在每次划分极不平衡时通过随机选择基准pivot可以大大降低出现最坏情况的概率。在 partition 前随机选取一个下标randIndex将其与左端点交换然后再执行常规的 partition 逻辑。这样期望时间复杂度为 O(n log n)且避免了有序输入时的退化。实现时用递归或迭代均可。​​​​​​​解题代码var sortArray function(nums) { const quickSort (arr, left, right) { if (left right) return; const pivotIndex randomizedPartition(arr, left, right); quickSort(arr, left, pivotIndex - 1); quickSort(arr, pivotIndex 1, right); }; quickSort(nums, 0, nums.length - 1); return nums; };例题蒙特卡洛方法估算π非LeetCode但为典型应用可作为扩展知识不强制要求。五、总结思想核心技巧时间复杂度适用场景滑动窗口双指针维护窗口O(n)子串/子数组最值、覆盖双指针相向或同向移动O(n)有序数组、链表环位运算二进制位操作O(1) 或 O(n)状态压缩、快速判断随机化算法引入随机性期望 O(n)避免最坏情况、近似求解 面试常见问题滑动窗口和双指针的区别滑动窗口是双指针的一种特殊形式窗口通常维护一个区间且窗口大小可变双指针更广泛包括快慢指针、相向指针等。n (n-1)的作用是什么将 n 的二进制表示中最低位的 1 变成 0常用于统计 1 的个数或判断是否为 2 的幂。布隆过滤器为什么会有误判多个元素经过哈希函数可能会将位数组的某些位置同时置为 1导致判断时可能误认为元素存在。随机化算法的优缺点优点简化实现、避免最坏情况、期望效率高缺点可能引入不确定性和小概率错误。 全系列完结至此我们的算法系列文章已覆盖排序算法查找算法图论算法动态规划字符串匹配数论与数学算法计算几何高级数据结构其他重要思想感谢你的陪伴如果你觉得这些文章对你有帮助欢迎在 CSDN 上分享你的学习心得也欢迎持续关注我的后续更新。如果你对某个专题还有疑问或希望深入某个具体算法欢迎随时交流