1.数组

约 1547 字大约 5 分钟

2026-04-09

笔记

本文的提到的数组刷题方法、口诀等均由 AI 生成。

刷题口诀：

前缀和，区间求和秒出。
差分数组，区间加减不累。
双指针，左右夹逼最稳。
滑动窗口，最长最短不晕。
二分答案，猜数游戏赢麻。
单调栈，Next Great 神器。
位运算，状态压缩省内存。

前缀和

题单

前缀和：开 n+1 数组，pre[i]=nums前i项和，区间[l,r]和=pre[r+1]-pre[l]。

public class LC_303 {
    private int[] pre;

    public LC_303(int[] nums) {
        int n = nums.length;
        pre = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            pre[i + 1] = pre[i] + nums[i];
        }
    }

    public int sumRange(int left, int right) {
        return pre[right + 1] - pre[left];
    }
}

差分数组

题单

区间两头标记 + 一次扫描还原；开 n+2 防越界；时间 O(n+m)，空间 O(n)。

public int[] corpFlightBookings(int[][] bookings, int n) {
    int[] diff = new int[n + 2];          // 1-index，多开 2 防越界
    // 1. 差分标记
    for (int[] b : bookings) {
        int first = b[0], last = b[1], seats = b[2];
        diff[first] += seats;             // 起点倒 seats
        if (last + 1 <= n) diff[last + 1] -= seats; // 终点后一桶减回去
    }
    // 2. 还原结果
    int[] ans = new int[n];
    int cur = 0;                          // 滚动累加器
    for (int i = 1; i <= n; i++) {
        cur += diff[i];                   // 当前桶水量
        ans[i - 1] = cur;                 // 转成 0-index 输出
    }
    return ans;
}

双指针

题单

public int[] twoSum(int[] nums, int target) {
    int l = 0, r = nums.length - 1;          // 0-index 头尾
    while (l < r) {
        int sum = nums[l] + nums[r];
        if (sum == target) return new int[]{l + 1, r + 1}; // 题目要 1-index
        else if (sum < target) l++;        // 和小，左指针右移
        else r--;                          // 和大，右指针左移
    }
    return new int[]{-1, -1};              // 题目保证有解，不会走到
}

滑动窗口

题单

public double findMaxAverage(int[] nums, int k) {
    int sum = 0, n = nums.length;
    // 1. 初始窗口 [0..k-1]
    for (int i = 0; i < k; i++) sum += nums[i];
    int maxSum = sum;
    // 2. 滑动窗口右移
    for (int i = k; i < n; i++) {
        sum = sum - nums[i - k] + nums[i]; // 减去左边出去，加上右边进来
        maxSum = Math.max(maxSum, sum);
    }
    return maxSum * 1.0 / k;               // 题目要平均值
}

二分查找

题单

闭区间 while (l <= r)

搜索范围两端都闭，终止 l = r+1；适合找精确值或插入位置。

while (l <= r) {
    int m = l + (r - l) / 2;
    if (nums[m] == target) return m;
    else if (nums[m] < target) l = m + 1;
    else r = m - 1;
}

左闭右开 while (l < r)

搜索范围 [l, r)，终止 l == r；适合猜最小可行答案。

模板：

while (l < r) {
    int m = l + (r - l) / 2;
    if (can(m)) r = m;   // 可行，保留 m
    else l = m + 1;      // 不可行，丢弃 m
}
// l 即答案

找值用 <=，猜值用 <；边界不同，千万别混。

单调栈

笔记

概念

单调栈 = 每次新元素入栈前，把破坏单调性的旧元素全踢出去，并记录“被踢者的下一个更大/更小值”就是当前新元素；

题单

模板

public int[] nextGreaterElement(int[] nums1, int[] nums2) {
    Map<Integer, Integer> map = new HashMap<>(); // num -> next greater
    Deque<Integer> st = new ArrayDeque<>();      // 单调递减栈（存值）

    for (int v : nums2) {            // ① 正序扫 nums2
        while (!st.isEmpty() && st.peek() < v) { // ② 栈顶比当前小
            map.put(st.pop(), v);    // ③ 当前 v 就是它的 next greater
        }
        st.push(v);                  // ④ 自己入栈，保持单调递减
    }
    // 栈内剩余元素无 next greater，默认为 -1
    int[] ans = new int[nums1.length];
    for (int i = 0; i < nums1.length; i++) {
        ans[i] = map.getOrDefault(nums1[i], -1);
    }
    return ans;
}

位运算

题单

模板

public int singleNumber(int[] nums) {
    int ans = 0;
    for (int v : nums) ans ^= v;   // 全员异或，偶数次抵消
    return ans;
}

版权所有

版权归属：FelixJY

许可证：署名-禁止演绎 4.0 国际 (CC-BY-ND-4.0)