数组算法总结：二分查找、快慢指针、双指针与滑动窗口

C++

#include <iostream>
#include <vector>
using namespace std;

int search(vector<int>& nums, int target) {
    // 初始化左闭右闭区间 [left, right]
    int left = 0;
    int right = nums.size() - 1;
    // 区间有效时循环
    while (left <= right) {
        // 计算 mid，避免溢出
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;  // 找到目标
        } else if (nums[mid] < target) {
            left = mid + 1;  // 目标在右半区
        } else {
            right = mid - 1;  // 目标在左半区
        }
    }
    return -1;  // 未找到
}

Go

package main
import "fmt"

func search(nums []int, target int) int {
    // 初始化左闭右闭区间 [left, right]
    left, right := 0, len(nums)-1
    // 区间有效时循环
    for left <= right {
        // 计算 mid，避免溢出（Go 中 int 随系统，64 位系统无溢出，但保持通用）
        mid := left + (right - left) / 2
        if nums[mid] == target {
            return mid  // 找到目标
        } else if nums[mid] < target {
            left = mid + 1  // 目标在右半区
        } else {
            right = mid - 1  // 目标在左半区
        }
    }
    return -1  // 未找到
}

由于该题目的区间是闭区间，因此中间的值是可以取到的。在一般的实际情况中，最常见的是左闭右开区间即 [left, right)，其中间值则无法取到，因此循环条件会发生改变，即只需要改成 while(left<right) 即可，因为 left==right 无意义。将 left=mid+1 改为 left=mid+1, right=mid-1 即可，代码不再赘述。

二、快慢指针（LeetCode 27）

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

• 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
• 返回 k。

这道题如果使用暴力解法直接遍历每个区间，时间复杂度为 O(n*n)，其在 LeetCode 上是可以通过的，但是此题还有一个更为高效的方法，那就是快慢指针。

核心解题思路（快慢指针法）

这是本题的最优解法（时间复杂度 O(n)，空间复杂度 O(1)），核心是用两个指针分工：

1. 慢指针（slow）：记录「非 val 元素」的存放位置，初始为 0；
2. 快指针（fast）：遍历整个数组，逐个检查元素，初始为 0；
3. 遍历过程中，若快指针指向的元素 ≠ val，则将该元素赋值给慢指针位置，慢指针右移；若等于 val，则快指针直接跳过；
4. 遍历结束后，慢指针的位置（索引）就是非 val 元素的数量 k。

这种方法无需删除元素，仅通过「覆盖」实现原地修改，完全满足题目要求。

Python

def removeElement(nums: list[int], val: int) -> int:
    # 慢指针：初始指向第一个位置（非 val 元素的存放位置）
    slow = 0
    # 快指针：遍历整个数组
    for fast in range(len(nums)):
        # 快指针找到非 val 元素，赋值给慢指针位置
        if nums[fast] != val:
            nums[slow] = nums[fast]
            slow += 1  # 慢指针右移，准备存下一个非 val 元素
    # 慢指针的最终值就是非 val 元素的数量
    return slow

Java

public class RemoveElement {
    public static int removeElement(int[] nums, int val) {
        // 慢指针初始为 0
        int slow = 0;
        // 快指针遍历数组
        for (int fast = 0; fast < nums.length; fast++) {
            // 快指针找到非 val 元素，赋值给慢指针位置
            if (nums[fast] != val) {
                nums[slow] = nums[fast];
                slow++;  // 慢指针右移
            }
        }
        // 返回非 val 元素数量
        return slow;
    }
}

C++

#include <iostream>
#include <vector>
using namespace std;

int removeElement(vector<int>& nums, int val) {
    // 慢指针初始为 0
    int slow = 0;
    // 快指针遍历数组
    for (int fast = 0; fast < nums.size(); fast++) {
        // 快指针找到非 val 元素，赋值给慢指针位置
        if (nums[fast] != val) {
            nums[slow] = nums[fast];
            slow++;  // 慢指针右移
        }
    }
    // 返回非 val 元素数量
    return slow;
}

Go

package main
import "fmt"

func removeElement(nums []int, val int) int {
    // 慢指针初始为 0
    slow := 0
    // 快指针遍历数组
    for fast := 0; fast < len(nums); fast++ {
        // 快指针找到非 val 元素，赋值给慢指针位置
        if nums[fast] != val {
            nums[slow] = nums[fast]
            slow++  // 慢指针右移
        }
    }
    // 返回非 val 元素数量
    return slow
}

三、双指针（LeetCode 997）

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

这道题最容易想到的思路就是先将每个数组中的元素进行平方，然后再进行排序，这种思路是最简单的。下面介绍一个更高效的方法：双指针。

核心解题思路（双指针法）

原数组是非递减的，但包含负数，平方后最大的值一定出现在数组的两端（如 -5 平方是 25，比 3 平方的 9 大）。因此：

1. 初始化左指针 left 指向数组开头，右指针 right 指向数组末尾；
2. 初始化结果数组 res，长度和原数组一致，用一个指针 k 从末尾向前填充（先放最大的平方值）；
3. 比较 nums[left] 和 nums[right] 的绝对值：
   • 若 |nums[left]| > |nums[right]|，则将 nums[left]² 放入 res[k]，左指针右移；
   • 否则将 nums[right]² 放入 res[k]，右指针左移；
4. k 向前移动一位，直到左右指针相遇，最终 res 就是非递减的平方数组。

Python

def sortedSquares(nums: list[int]) -> list[int]:
    n = len(nums)
    res = [0] * n  # 初始化结果数组
    left, right = 0, n - 1  # 左右指针
    k = n - 1  # 结果数组的填充指针（从后往前）
    while left <= right:
        # 比较两端元素的绝对值
        left_sq = nums[left] ** 2
        right_sq = nums[right] ** 2
        if left_sq > right_sq:
            res[k] = left_sq
            left += 1  # 左指针右移
        else:
            res[k] = right_sq
            right -= 1  # 右指针左移
        k -= 1  # 填充指针左移
    return res

Java

public class SortedSquares {
    public static int[] sortedSquares(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];  // 初始化结果数组
        int left = 0, right = n - 1;  // 左右指针
        int k = n - 1;  // 填充指针
        while (left <= right) {
            int leftSq = nums[left] * nums[left];
            int rightSq = nums[right] * nums[right];
            if (leftSq > rightSq) {
                res[k] = leftSq;
                left++;
            } else {
                res[k] = rightSq;
                right--;
            }
            k--;
        }
        return res;
    }
}

C++

#include <iostream>
#include <vector>
using namespace std;

vector<int> sortedSquares(vector<int>& nums) {
    int n = nums.size();
    vector<int> res(n);  // 初始化结果数组
    int left = 0, right = n - 1;  // 左右指针
    int k = n - 1;  // 填充指针
    while (left <= right) {
        int leftSq = nums[left] * nums[left];
        int rightSq = nums[right] * nums[right];
        if (leftSq > rightSq) {
            res[k] = leftSq;
            left++;
        } else {
            res[k] = rightSq;
            right--;
        }
        k--;
    }
    return res;
}

Go

package main
import "fmt"

func sortedSquares(nums []int) []int {
    n := len(nums)
    res := make([]int, n)  // 初始化结果数组
    left, right := 0, n-1  // 左右指针
    k := n - 1  // 填充指针
    for left <= right {
        leftSq := nums[left] * nums[left]
        rightSq := nums[right] * nums[right]
        if leftSq > rightSq {
            res[k] = leftSq
            left++
        } else {
            res[k] = rightSq
            right--
        }
        k--
    }
    return res
}

四、滑动窗口（LeetCode 209）

核心解题思路（滑动窗口 / 双指针）

滑动窗口的核心是用两个指针维护一个「动态窗口」，通过扩张和收缩窗口找到满足条件的最小长度：

1. 右指针（right）：扩张窗口，逐个将元素加入窗口，累加窗口内元素和；
2. 左指针（left）：当窗口和≥target 时，收缩窗口（左指针右移），并更新最小窗口长度；
3. 遍历结束后，若找到有效窗口则返回最小长度，否则返回 0。

Python

def minSubArrayLen(target: int, nums: list[int]) -> int:
    n = len(nums)
    min_len = float('inf')  # 初始化为无穷大，记录最小长度
    left = 0  # 左指针，窗口左边界
    current_sum = 0  # 窗口内元素和
    for right in range(n):
        # 右指针扩张窗口
        current_sum += nums[right]
        # 窗口和≥target 时，收缩左指针，优化最小长度
        while current_sum >= target:
            min_len = min(min_len, right - left + 1)  # 更新最小长度
            current_sum -= nums[left]  # 左指针右移，移出窗口
            left += 1
    # 若 min_len 仍为无穷大，说明无符合条件的子数组，返回 0；否则返回 min_len
    return min_len if min_len != float('inf') else 0

Java

public class MinSubArrayLen {
    public static int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        int minLen = Integer.MAX_VALUE;  // 初始化为整型最大值
        int left = 0;  // 左指针
        int currentSum = 0;  // 窗口和
        for (int right = 0; right < n; right++) {
            // 右指针扩张
            currentSum += nums[right];
            // 收缩左指针，优化最小长度
            while (currentSum >= target) {
                minLen = Math.min(minLen, right - left + 1);
                currentSum -= nums[left];
                left++;
            }
        }
        // 无符合条件的子数组返回 0，否则返回 minLen
        return minLen == Integer.MAX_VALUE ? 0 : minLen;
    }
}

C++

#include <iostream>
#include <vector>
#include <climits>  // 包含 INT_MAX
using namespace std;

int minSubArrayLen(int target, vector<int>& nums) {
    int n = nums.size();
    int minLen = INT_MAX;  // 初始化为整型最大值
    int left = 0;  // 左指针
    int currentSum = 0;  // 窗口和
    for (int right = 0; right < n; right++) {
        // 右指针扩张
        currentSum += nums[right];
        // 收缩左指针，优化最小长度
        while (currentSum >= target) {
            minLen = min(minLen, right - left + 1);
            currentSum -= nums[left];
            left++;
        }
    }
    // 无符合条件的子数组返回 0，否则返回 minLen
    return minLen == INT_MAX ? 0 : minLen;
}

Go

package main
import (
    "fmt"
    "math"
)

func minSubArrayLen(target int, nums []int) int {
    n := len(nums)
    minLen := math.MaxInt32  // 初始化为 int32 最大值
    left := 0  // 左指针
    currentSum := 0  // 窗口和
    for right := 0; right < n; right++ {
        // 右指针扩张
        currentSum += nums[right]
        // 收缩左指针，优化最小长度
        for currentSum >= target {
            if right-left+1 < minLen {
                minLen = right - left + 1
            }
            currentSum -= nums[left]
            left++
        }
    }
    // 无符合条件的子数组返回 0，否则返回 minLen
    if minLen == math.MaxInt32 {
        return 0
    }
    return minLen
}

五、总结

这四种算法是操作数组常用的算法，也是面试和笔试中常考的算法，能应用于大部分操作数组的情景。