标签： 前缀和

目标

一个 k x k 的 幻方 指的是一个 k x k 填满整数的方格阵，且每一行、每一列以及两条对角线的和 全部相等 。幻方中的整数 不需要互不相同 。显然，每个 1 x 1 的方格都是一个幻方。

给你一个 m x n 的整数矩阵 grid ，请你返回矩阵中 最大幻方 的 尺寸 （即边长 k）。

示例 1：

输入：grid = [[7,1,4,5,6],[2,5,1,6,4],[1,5,4,3,2],[1,2,7,3,4]]
输出：3
解释：最大幻方尺寸为 3 。
每一行，每一列以及两条对角线的和都等于 12 。
- 每一行的和：5+1+6 = 5+4+3 = 2+7+3 = 12
- 每一列的和：5+5+2 = 1+4+7 = 6+3+3 = 12
- 对角线的和：5+4+3 = 6+4+2 = 12

示例 2：

输入：grid = [[5,1,3,1],[9,3,3,1],[1,3,3,8]]
输出：2

说明：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 50
• 1 <= grid[i][j] <= 10^6

思路

找出 m x n 矩阵中的最大幻方的边长。

暴力枚举顶点与边长，判断是否是幻方。可以记录水平、垂直、主对角线和副对角线上的前缀和，方便幻方判断。另外边长可以从大到小枚举，是幻方就直接返回。

代码

/**
 * @date 2026-01-19 14:59
 */
public class LargestMagicSquare1895 {

    public int largestMagicSquare(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int res = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int l = Math.min(i, j) + 1;
                for (int k = res + 1; k <= l; k++) {
                    if (isMagicSquare(grid, i, j, k)) {
                        res = k;
                    }
                }
            }
        }
        return res;
    }

    public boolean isMagicSquare(int[][] grid, int x, int y, int l) {
        int diagonal1 = 0;
        int diagonal2 = 0;
        for (int k = 0; k < l; k++) {
            diagonal1 += grid[x - k][y - k];
            diagonal2 += grid[x - l + 1 + k][y - k];
        }
        if (diagonal1 != diagonal2) {
            return false;
        }

        for (int i = x - l + 1; i <= x; i++) {
            int sum = 0;
            for (int j = y - l + 1; j <= y; j++) {
                sum += grid[i][j];
            }
            if (sum != diagonal1) {
                return false;
            }
        }
        for (int j = y - l + 1; j <= y; j++) {
            int sum = 0;
            for (int i = x - l + 1; i <= x; i++) {
                sum += grid[i][j];
            }
            if (sum != diagonal1) {
                return false;
            }
        }
        return true;
    }

}

性能

目标

给你一个顾客访问商店的日志，用一个下标从 0 开始且只包含字符 'N' 和 'Y' 的字符串 customers 表示：

• 如果第 i 个字符是 'Y' ，它表示第 i 小时有顾客到达。
• 如果第 i 个字符是 'N' ，它表示第 i 小时没有顾客到达。

如果商店在第 j 小时关门（0 <= j <= n），代价按如下方式计算：

• 在开门期间，如果某一个小时没有顾客到达，代价增加 1 。
• 在关门期间，如果某一个小时有顾客到达，代价增加 1 。

请你返回在确保代价 最小 的前提下，商店的 最早 关门时间。

注意，商店在第 j 小时关门表示在第 j 小时以及之后商店处于关门状态。

示例 1：

输入：customers = "YYNY"
输出：2
解释：
- 第 0 小时关门，总共 1+1+0+1 = 3 代价。
- 第 1 小时关门，总共 0+1+0+1 = 2 代价。
- 第 2 小时关门，总共 0+0+0+1 = 1 代价。
- 第 3 小时关门，总共 0+0+1+1 = 2 代价。
- 第 4 小时关门，总共 0+0+1+0 = 1 代价。
在第 2 或第 4 小时关门代价都最小。由于第 2 小时更早，所以最优关门时间是 2 。

示例 2：

输入：customers = "NNNNN"
输出：0
解释：最优关门时间是 0 ，因为自始至终没有顾客到达。

示例 3：

输入：customers = "YYYY"
输出：4
解释：最优关门时间是 4 ，因为每一小时均有顾客到达。

说明：

• 1 <= customers.length <= 10^5
• customers 只包含字符 'Y' 和 'N' 。

思路

有一个顾客访问日志 customers，customers[i] 表示在第 i 小时是否有顾客到达，关店代价的计算方式为，营业期间没有顾客到达或者关店后（包括关店的时刻）有顾客到达代价 +1。返回代价最小的最早关门时间。

前后缀分解，前缀记录没有顾客到达的数量，后缀记录有顾客到达的数量。

代码

/**
 * @date 2025-12-26 8:57
 */
public class BestClosingTime2483 {

    public int bestClosingTime(String customers) {
        int n = customers.length();
        int[] prefix = new int[n + 1];
        int[] suffix = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + (customers.charAt(i) == 'N' ? 1 : 0);
            suffix[n - i - 1] = suffix[n - i] + (customers.charAt(n - i - 1) == 'Y' ? 1 : 0);
        }
        int min = Integer.MAX_VALUE;
        int res = 0;
        for (int i = 0; i <= n; i++) {
            int cost = prefix[i] + suffix[i];
            if (min > cost) {
                res = i;
                min = cost;
            }
        }
        return res;
    }

}

性能

目标

给你两个整数数组 prices 和 strategy，其中：

• prices[i] 表示第 i 天某股票的价格。
• strategy[i] 表示第 i 天的交易策略，其中：
  • -1 表示买入一单位股票。
  • 0 表示持有股票。
  • 1 表示卖出一单位股票。

同时给你一个 偶数 整数 k，你可以对 strategy 进行 最多一次 修改。一次修改包括：

• 选择 strategy 中恰好 k 个 连续 元素。
• 将前 k / 2 个元素设为 0（持有）。
• 将后 k / 2 个元素设为 1（卖出）。

利润 定义为所有天数中 strategy[i] * prices[i] 的 总和 。

返回你可以获得的 最大 可能利润。

注意： 没有预算或股票持有数量的限制，因此所有买入和卖出操作均可行，无需考虑过去的操作。

示例 1：

输入： prices = [4,2,8], strategy = [-1,0,1], k = 2
输出： 10
解释：
修改 策略 利润计算 利润
原始 [-1, 0, 1] (-1 × 4) + (0 × 2) + (1 × 8) = -4 + 0 + 8 4
修改 [0, 1] [0, 1, 1] (0 × 4) + (1 × 2) + (1 × 8) = 0 + 2 + 8 10
修改 [1, 2] [-1, 0, 1] (-1 × 4) + (0 × 2) + (1 × 8) = -4 + 0 + 8 4
因此，最大可能利润是 10，通过修改子数组 [0, 1] 实现。

示例 2：

输入： prices = [5,4,3], strategy = [1,1,0], k = 2
输出： 9
解释：
修改 策略 利润计算 利润
原始 [1, 1, 0] (1 × 5) + (1 × 4) + (0 × 3) = 5 + 4 + 0 9
修改 [0, 1] [0, 1, 0] (0 × 5) + (1 × 4) + (0 × 3) = 0 + 4 + 0 4
修改 [1, 2] [1, 0, 1] (1 × 5) + (0 × 4) + (1 × 3) = 5 + 0 + 3 8
因此，最大可能利润是 9，无需任何修改即可达成。

说明：

• 2 <= prices.length == strategy.length <= 10^5
• 1 <= prices[i] <= 10^5
• -1 <= strategy[i] <= 1
• 2 <= k <= prices.length
• k 是偶数

思路

定长滑动窗口，考虑窗口内现利润与原利润差值的最大值。维护窗口中间下标，调整后的利润从中间下标移出。使用一个变量记录窗口左端点原利润的前缀，另一个变量记录右端点的原利润前缀，相减可得窗口的原利润。原利润是根据策略累加，现利润是根据价格累加。

代码

/**
 * @date 2025-12-18 8:58
 */
public class MaxProfit3652 {

    public long maxProfit(int[] prices, int[] strategy, int k) {
        int n = prices.length;
        long cur = 0L, sum = 0L;
        for (int r = 0; r < k / 2; r++) {
            sum += prices[r] * strategy[r];
        }
        for (int r = k / 2; r < k; r++) {
            sum += prices[r] * strategy[r];
            cur += prices[r];
        }
        long diff = cur - sum;
        long prefix = 0L;
        int l = 0, m = k / 2;
        for (int r = k; r < n; r++) {
            sum += prices[r] * strategy[r];
            cur += prices[r] - prices[m++];
            prefix += prices[l] * strategy[l];
            l++;
            diff = Math.max(diff, cur - sum + prefix);
        }
        return sum + Math.max(0, diff);
    }

}

性能

目标

给你一个二维整数数组 points，其中 points[i] = [xi, yi] 表示第 i 个点在笛卡尔平面上的坐标。

水平梯形 是一种凸四边形，具有 至少一对 水平边（即平行于 x 轴的边）。两条直线平行当且仅当它们的斜率相同。

返回可以从 points 中任意选择四个不同点组成的 水平梯形 数量。

由于答案可能非常大，请返回结果对 10^9 + 7 取余数后的值。

示例 1：

输入： points = [[1,0],[2,0],[3,0],[2,2],[3,2]]
输出： 3
解释：
有三种不同方式选择四个点组成一个水平梯形：
使用点 [1,0]、[2,0]、[3,2] 和 [2,2]。
使用点 [2,0]、[3,0]、[3,2] 和 [2,2]。
使用点 [1,0]、[3,0]、[3,2] 和 [2,2]。

示例 2：

输入： points = [[0,0],[1,0],[0,1],[2,1]]
输出： 1
解释：
只有一种方式可以组成一个水平梯形。

说明：

• 4 <= points.length <= 10^5
• –10^8 <= xi, yi <= 10^8
• 所有点两两不同。

思路

有一些二维平面中的点 points，从中选取四个点组成水平梯形，返回水平梯形的数目。

水平梯形是有一对边平行于 x 轴的梯形。直接的想法是根据纵坐标分组，选两组，每组中选两个点。

可以直接计算每组的组合数 C(n, 2) = n * (n - 1) / 2，计算分组组合数的后缀和，根据乘法原理计算即可。

代码

/**
 * @date 2025-12-02 0:14
 */
public class CountTrapezoids2623 {

    /**
     * 执行通过
     */
    public int countTrapezoids(int[][] points) {
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int[] point : points) {
            cnt.merge(point[1], 1, Integer::sum);
        }
        int mod = 1000000007;
        for (Map.Entry<Integer, Integer> entry : cnt.entrySet()) {
            Integer c = entry.getValue();
            cnt.put(entry.getKey(), (int) ((c * (c - 1L) / 2) % mod));
        }
        int[] comb = cnt.values().stream().mapToInt(x -> x).toArray();
        int n = comb.length;
        int[] suffix = new int[n + 1];
        for (int i = n - 1; i >= 0; i--) {
            suffix[i] = (suffix[i + 1] + comb[i]) % mod;
        }
        long res = 0L;
        for (int i = 0; i < n; i++) {
            res = (res + ((long) comb[i] * suffix[i + 1])) % mod;
        }
        return (int) res;
    }
}

性能

目标

给你一个正整数数组 nums，请你移除 最短 子数组（可以为 空），使得剩余元素的 和 能被 p 整除。 不允许 将整个数组都移除。

请你返回你需要移除的最短子数组的长度，如果无法满足题目要求，返回 -1 。

子数组 定义为原数组中连续的一组元素。

示例 1：

输入：nums = [3,1,4,2], p = 6
输出：1
解释：nums 中元素和为 10，不能被 p 整除。我们可以移除子数组 [4] ，剩余元素的和为 6 。

示例 2：

输入：nums = [6,3,5,2], p = 9
输出：2
解释：我们无法移除任何一个元素使得和被 9 整除，最优方案是移除子数组 [5,2] ，剩余元素为 [6,3]，和为 9 。

示例 3：

输入：nums = [1,2,3], p = 3
输出：0
解释：和恰好为 6 ，已经能被 3 整除了。所以我们不需要移除任何元素。

示例 4：

输入：nums = [1,2,3], p = 7
输出：-1
解释：没有任何方案使得移除子数组后剩余元素的和被 7 整除。

示例 5：

输入：nums = [1000000000,1000000000,1000000000], p = 3
输出：0

说明：

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9
• 1 <= p <= 10^9

思路

有一个正整数数组 nums，需要移除一个最短子数组（可以为空），使得剩余元素的和能被 p 整除，返回移除的最短子数组长度，如果无法满足返回 -1。

计算数组和，求出余数 rem，使用哈希表 lastIndex 记录前缀和余数的最大下标，根据当前前缀和的余数，计算需要保留的前缀数组 [0, lastIndex.get((curRem - rem + p) % p)]，计算得到需要减去的子数组 [lastIndex.get((curRem - rem + p) % p) + 1, i] 它的和模 p 余 rem，取长度的最小值即可。

代码

/**
 * @date 2025-11-30 10:41
 */
public class MinSubarray1590 {

    public int minSubarray(int[] nums, int p) {
        int n = nums.length;
        long sum = 0;
        for (int num : nums) {
            sum += num;
        }
        int rem = (int) (sum % p);
        if (rem == 0) {
            return 0;
        }
        Map<Integer, Integer> lastIndex = new HashMap<>();
        lastIndex.putIfAbsent(0, -1);
        int curRem = 0;
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            curRem = (curRem + nums[i]) % p;
            int prev = (p + curRem - rem) % p;
            res = Math.min(res, i - lastIndex.getOrDefault(prev, -n));
            lastIndex.put(curRem, i);
        }
        return res == n ? -1 : res;
    }

}

性能

目标

给你一个整数数组 nums 和一个整数 k 。

返回 nums 中一个 非空子数组 的 最大 和，要求该子数组的长度可以 被 k 整除。

示例 1：

输入： nums = [1,2], k = 1
输出： 3
解释：
子数组 [1, 2] 的和为 3，其长度为 2，可以被 1 整除。

示例 2：

输入： nums = [-1,-2,-3,-4,-5], k = 4
输出： -10
解释：
满足题意且和最大的子数组是 [-1, -2, -3, -4]，其长度为 4，可以被 4 整除。

示例 3：

输入： nums = [-5,1,2,-3,4], k = 2
输出： 4
解释：
满足题意且和最大的子数组是 [1, 2, -3, 4]，其长度为 4，可以被 2 整除。

说明：

• 1 <= k <= nums.length <= 2 * 10^5
• -10^9 <= nums[i] <= 10^9

思路

计算长度能被 k 整除的子数组的最大元素和。

核心点是维护同余前缀和的最小值。

也有网友使用滑窗加动态规划来做，滑窗计算 长度为 k 的子数组和，动态规划累加长度 m * k 的子数组和，这里使用了贪心策略，如果前面的子数组和小于 0，直接重置为 0。

代码

/**
 * @date 2025-11-27 9:06
 */
public class MaxSubarraySum3381 {

    public long maxSubarraySum(int[] nums, int k) {
        int n = nums.length;
        long[] prefix = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            prefix[i] = prefix[i - 1] + nums[i - 1];
        }
        long[] minPrefix = new long[k];
        Arrays.fill(minPrefix, Long.MAX_VALUE / 2);
        long res = Long.MIN_VALUE;
        for (int i = 0; i <= n; i++) {
            int rem = i % k;
            res = Math.max(res, prefix[i] - minPrefix[rem]);
            minPrefix[rem] = Math.min(minPrefix[rem], prefix[i]);
        }
        return res;
    }

}

性能

目标

给你一个字符串 s ，返回 s 中 长度为 3 的不同回文子序列 的个数。

即便存在多种方法来构建相同的子序列，但相同的子序列只计数一次。

回文 是正着读和反着读一样的字符串。

子序列 是由原字符串删除其中部分字符（也可以不删除）且不改变剩余字符之间相对顺序形成的一个新字符串。

例如，"ace" 是 "abcde" 的一个子序列。

示例 1：

输入：s = "aabca"
输出：3
解释：长度为 3 的 3 个回文子序列分别是：
- "aba" ("aabca" 的子序列)
- "aaa" ("aabca" 的子序列)
- "aca" ("aabca" 的子序列)

示例 2：

输入：s = "adc"
输出：0
解释："adc" 不存在长度为 3 的回文子序列。

示例 3：

输入：s = "bbcbaba"
输出：4
解释：长度为 3 的 4 个回文子序列分别是：
- "bbb" ("bbcbaba" 的子序列)
- "bcb" ("bbcbaba" 的子序列)
- "bab" ("bbcbaba" 的子序列)
- "aba" ("bbcbaba" 的子序列)

说明：

• 3 <= s.length <= 10^5
• s 仅由小写英文字母组成

思路

求长度为 3 的不同回文子序列个数。

枚举中间元素，同时枚举 a - z 作为左右两侧的字母，判断是否前后都存在。

对字母计数，在枚举过程中记录前面出现字母的次数，结合总次数可以快速判断后面是否存在相同的字母。注意，如果前面出现的字母与枚举的中间字母相同需要将次数减 1。

代码

/**
 * @date 2025-11-21 8:44
 */
public class CountPalindromicSubsequence1930 {

    public int countPalindromicSubsequence_v1(String s) {
        int[] total = new int[26];
        char[] chars = s.toCharArray();
        for (char c : chars) {
            total[c - 'a']++;
        }
        boolean[][] visited = new boolean[26][26];
        int[] prefix = new int[26];
        int res = 0;
        for (char c : chars) {
            prefix[c - 'a']++;
            for (int j = 0; j < 26; j++) {
                if (!visited[j][c - 'a'] && total[j] > prefix[j] && ((j == c - 'a' && prefix[j] > 1) || j != c - 'a' && prefix[j] > 0)) {
                    visited[j][c - 'a'] = true;
                    res++;
                }
            }
        }
        return res;
    }

}

性能

目标

给你一个 二进制字符串 s。

你可以对这个字符串执行 任意次 下述操作：

• 选择字符串中的任一下标 i（ i + 1 < s.length ），该下标满足 s[i] == '1' 且 s[i + 1] == '0'。
• 将字符 s[i] 向 右移 直到它到达字符串的末端或另一个 '1'。例如，对于 s = "010010"，如果我们选择 i = 1，结果字符串将会是 s = "000110"。

返回你能执行的 最大 操作次数。

示例 1：

输入： s = "1001101"
输出： 4
解释：
可以执行以下操作：
选择下标 i = 0。结果字符串为 s = "0011101"。
选择下标 i = 4。结果字符串为 s = "0011011"。
选择下标 i = 3。结果字符串为 s = "0010111"。
选择下标 i = 2。结果字符串为 s = "0001111"。

示例 2：

输入： s = "00111"
输出： 0

说明：

• 1 <= s.length <= 10^5
• s[i] 为 '0' 或 '1'。

思路

有一个二进制字符串 s，每次操作可以选择一个下标 i，满足 s[i] == '1' 且 s[i + 1] == '0'，将 s[i] 向右移直到遇到另一个 1 或者到达末尾，返回可以执行的最大操作次数。

要使操作次数最大，每组相邻的 0 都要为其前面的 1 提供一次操作。换句话说操作尽量不要让右侧的 0 过早的合并，累加每组相邻的 0 前面 1 的个数即可。

计算前缀 1 个数，正序遍历，第一次遇到 0 时，就加上前面 1 的个数，跳过相邻的 0（因为每次操作都要移到最右侧，相邻的 0 对每个 1 只能贡献一次操作）。

代码

/**
 * @date 2025-11-13 8:44
 */
public class MaxOperations3228 {

    public int maxOperations(String s) {
        int n = s.length();
        char[] chars = s.toCharArray();
        int[] prefix = new int[n + 1];
        int res = 0;
        for (int i = 1; i <= n; i++) {
            prefix[i] = prefix[i - 1] + (chars[i - 1] - '0');
        }
        int i = 0;
        while (i < n) {
            if (chars[i] == '0') {
                res += prefix[i];
            }
            while (i < n && chars[i++] == '0') {
            }
        }
        return res;
    }

}

性能