📝 写在前面

在算法设计中，除了经典的数据结构和算法模型，还有一些精妙的“思想”能让我们以简洁的方式解决问题。它们往往不需要复杂的数据结构，只需巧妙地利用指针移动、二进制特性或概率方法，就能高效解题。

本文带你系统学习四种重要思想：

  • 滑动窗口：在数组/字符串上维护一个动态窗口，解决子数组/子串问题

  • 双指针：利用两个指针从两端或同向遍历，减少循环嵌套

  • 位运算：利用二进制位的特性，实现高效判断、状态压缩

  • 随机化算法：用概率方法近似求解或优化确定性算法

每部分均包含 一句话记住、核心思想、流程图推荐、代码实现、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/

💻 代码实现（两数之和 II）

function 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 - 输入有序数组

解题思路
利用数组有序的性质，使用相向双指针。初始化 left=0，right=n-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⊕a=0，a⊕0=a，且满足交换律和结合律。将所有数字异或起来，成对出现的数字会抵消为 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/

💻 代码实现（随机化快速排序的 partition）

function 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) 避免最坏情况、近似求解

📌 面试常见问题

  1. 滑动窗口和双指针的区别？

    • 滑动窗口是双指针的一种特殊形式，窗口通常维护一个区间，且窗口大小可变；双指针更广泛，包括快慢指针、相向指针等。

  2. n & (n-1) 的作用是什么？

    • 将 n 的二进制表示中最低位的 1 变成 0，常用于统计 1 的个数或判断是否为 2 的幂。

  3. 布隆过滤器为什么会有误判？

    • 多个元素经过哈希函数可能会将位数组的某些位置同时置为 1，导致判断时可能误认为元素存在。

  4. 随机化算法的优缺点？

    • 优点：简化实现、避免最坏情况、期望效率高；缺点：可能引入不确定性和小概率错误。

🎯 全系列完结

至此，我们的算法系列文章已覆盖：

  • 排序算法

  • 查找算法

  • 图论算法

  • 动态规划

  • 字符串匹配

  • 数论与数学算法

  • 计算几何

  • 高级数据结构

  • 其他重要思想

感谢你的陪伴！如果你觉得这些文章对你有帮助，欢迎在 CSDN 上分享你的学习心得，也欢迎持续关注我的后续更新。

如果你对某个专题还有疑问，或希望深入某个具体算法，欢迎随时交流～

# 算法 # java # 数据结构 # 动态规划
Logo
AtomGit开源社区

AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。

更多推荐

cover

G-Star 精选开源项目推荐｜第二十二期

avatar AtomGit开源社区
cover

CANN 开发者 Meetup · 杭州模型专场｜线下技术沙龙正式开启报名！

avatar AtomGit开源社区
cover

14.4 万奖金！昇腾 Model Agent 模型适配大赛正式起航（第二季）

avatar AtomGit开源社区