标签： 前缀和

目标

给你一个下标从 0 开始的整数数组 nums 。现有一个长度等于 nums.length 的数组 arr 。对于满足 nums[j] == nums[i] 且 j != i 的所有 j ，arr[i] 等于所有 |i - j| 之和。如果不存在这样的 j ，则令 arr[i] 等于 0 。

返回数组 arr 。

示例 1：

输入：nums = [1,3,1,1,2]
输出：[5,0,3,4,0]
解释：
i = 0 ，nums[0] == nums[2] 且 nums[0] == nums[3] 。因此，arr[0] = |0 - 2| + |0 - 3| = 5 。 
i = 1 ，arr[1] = 0 因为不存在值等于 3 的其他下标。
i = 2 ，nums[2] == nums[0] 且 nums[2] == nums[3] 。因此，arr[2] = |2 - 0| + |2 - 3| = 3 。
i = 3 ，nums[3] == nums[0] 且 nums[3] == nums[2] 。因此，arr[3] = |3 - 0| + |3 - 2| = 4 。 
i = 4 ，arr[4] = 0 因为不存在值等于 2 的其他下标。

示例 2：

输入：nums = [0,5,3]
输出：[0,0,0]
解释：因为 nums 中的元素互不相同，对于所有 i ，都有 arr[i] = 0 。

说明：

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

思路

有一个整数数组 nums，返回一个等长数组 arr，arr[i] 等于所有与 nums[i] 相等的 nums[j] 到下标 i 的距离之和，即 Σ|i - j|，如果不存在这样的 j 则距离为 0。

使用哈希表将元素分组，假定某一组内的元素为 a0 < a1 < …… < a_(m - 1)，令 S0 = Σ_(j ∈ [0, m - 1])(aj - a0)，考虑 S1 - S0，原来所有元素到 a0 的距离变成了所有元素到 a1 的距离：组内下标小于 1 的距离都增加了 a1 - a0，组内下标大于等于 1 的距离都减少了 a1 - a0。

更一般的情况 Si - S_(i - 1)，组内下标小于 i 的元素到 a_(i - 1) 的距离都增加了 a_i - a_(i - 1)，组内下标大于等于 i 的元素到 a_(i - 1) 的距离都减小了 a_i - a_(i - 1)。组内下标小于 i 的元素有 i 个，组内下标大于等于 i 的元素有 m - i 个，Si - S_(i - 1) = i * (ai - a_(i - 1)) - (m - i) * (ai - a_(i - 1)) = (2 * i - m) * (ai - a_(i - 1))。

代码

/**
 * @date 2026-04-23 9:46
 */
public class Distance2615 {

    public long[] distance(int[] nums) {
        int n = nums.length;
        long[] res = new long[n];
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            map.putIfAbsent(nums[i], new ArrayList<>());
            map.get(nums[i]).add(i);
        }
        for (List<Integer> list : map.values()) {
            if (list.size() > 1) {
                long s = 0L;
                int start = list.get(0);
                for (int i = 1; i < list.size(); i++) {
                    s += list.get(i) - start;
                }
                res[start] = s;
                for (int i = 1; i < list.size(); i++) {
                    res[list.get(i)] = res[list.get(i - 1)] + (2 * i - list.size()) * (list.get(i) - list.get(i - 1));
                }
            }
        }
        return res;
    }
}

性能

目标

给你一个由正整数组成的 m x n 矩阵 grid。你的任务是判断是否可以通过 一条水平或一条垂直分割线 将矩阵分割成两部分，使得：

• 分割后形成的每个部分都是 非空 的。
• 两个部分中所有元素的和 相等 。

如果存在这样的分割，返回 true；否则，返回 false。

示例 1：

输入： grid = [[1,4],[2,3]]
输出： true
解释：
在第 0 行和第 1 行之间进行水平分割，得到两个非空部分，每部分的元素之和为 5。因此，答案是 true。

示例 2：

输入： grid = [[1,3],[2,4]]
输出： false
解释：
无论是水平分割还是垂直分割，都无法使两个非空部分的元素之和相等。因此，答案是 false。

说明：

• 1 <= m == grid.length <= 10^5
• 1 <= n == grid[i].length <= 10^5
• 2 <= m * n <= 10^5
• 1 <= grid[i][j] <= 10^5

思路

有一个 m x n 矩阵，判断能否用一条水平线或者垂直线将矩阵分割成两部分，使得两部分的和相等，并且每一部分非空。

先求出总和，根据题意枚举所有分割水平线与垂直线判断两部分的和是否相等。

代码

/**
 * @date 2026-03-25 9:03
 */
public class CanPartitionGrid3546 {

    public boolean canPartitionGrid(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        long sum = 0L;
        for (int[] row : grid) {
            for (int num : row) {
                sum += num;
            }
        }
        if (sum % 2 == 1) {
            return false;
        }
        long half = sum / 2;
        long prefix = 0L;
        for (int i = 0; i < m - 1; i++) {
            for (int num : grid[i]) {
                prefix += num;
            }
            if (prefix << 1 == sum) {
                return true;
            } else if (prefix > half) {
                break;
            }
        }
        prefix = 0L;
        for (int j = 0; j < n - 1; j++) {
            for (int i = 0; i < m; i++) {
                prefix += grid[i][j];
            }
            if (prefix << 1 == sum) {
                return true;
            } else if (prefix > half) {
                break;
            }
        }
        return false;
    }

}

性能

目标

给你一个 m x n 的整数矩阵 grid 。

菱形和 指的是 grid 中一个正菱形 边界 上的元素之和。本题中的菱形必须为正方形旋转45度，且四个角都在一个格子当中。下图是四个可行的菱形，每个菱形和应该包含的格子都用了相应颜色标注在图中。

注意，菱形可以是一个面积为 0 的区域，如上图中右下角的紫色菱形所示。

请你按照 降序 返回 grid 中三个最大的 互不相同的菱形和 。如果不同的和少于三个，则将它们全部返回。

示例 1：

输入：grid = [[3,4,5,1,3],[3,3,4,2,3],[20,30,200,40,10],[1,5,5,4,1],[4,3,2,2,5]]
输出：[228,216,211]
解释：最大的三个菱形和如上图所示。
- 蓝色：20 + 3 + 200 + 5 = 228
- 红色：200 + 2 + 10 + 4 = 216
- 绿色：5 + 200 + 4 + 2 = 211

示例 2：

输入：grid = [[1,2,3],[4,5,6],[7,8,9]]
输出：[20,9,8]
解释：最大的三个菱形和如上图所示。
- 蓝色：4 + 2 + 6 + 8 = 20
- 红色：9 （右下角红色的面积为 0 的菱形）
- 绿色：8 （下方中央面积为 0 的菱形）

示例 3：

输入：grid = [[7,7,7]]
输出：[7]
解释：所有三个可能的菱形和都相同，所以返回 [7] 。

提示：

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

思路

有一个 m x n 矩阵 grid，返回矩阵中最大的三个 不相同 的菱形和。满足条件的菱形指矩阵内部的正方形顺时针旋转 45°，并且四个角必须占一个格子的正方形。菱形和就是其边界上的元素之和。

枚举所有合法的正菱形。针对每一个元素 (i, j)，枚举以它作为对角线交点的所有可能的正菱形（正方形）。

经过观察发现，如果边上元素个数为 k + 1，那么上顶点坐标为 (i - k, j)，下顶点坐标为 (i + k, j)，左顶点坐标为 (i, j - k)，右顶点坐标为 (i, j + k)。

枚举 (i, j) 所在行 [j - k, j + k] 范围内的元素。注意左右顶点的上下元素重合到自身，不能重复累加。特殊处理两端点，中间枚举 x ∈ [j - k + 1, j + k - 1] 累加上下 h 的元素值，即 (i - h, x) 与 (i + h, x)。其中 h = k - Math.abs(j - x)，k 表示中点到四个角的距离，x 表示列标，j - x 表示列标距离中点的距离。

上面的解法针对每一个中点重复累加了边上的元素和。更好做法是使用两个二维数组分别表示两个方向 ↘ ↙ 上截止到 (u, v) 的前缀和。中点确定之后，可以确定边的四个角，进而可以计算前缀和。注意不要重复计算四个角。

代码

/**
 * @date 2026-03-16 9:37
 */
public class GetBiggestThree1878 {

    public int[] getBiggestThree(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        TreeSet<Integer> set = new TreeSet<>((a, b) -> b - a);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; i + k < m && i - k >= 0 && j - k >= 0 && j + k < n; k++) {
                    int sum = 0;
                    if (k == 0) {
                        set.add(grid[i][j]);
                        continue;
                    }
                    sum += grid[i][j - k] + grid[i][j + k];
                    for (int x = j - k + 1; x <= j + k - 1; x++) {
                        int h = k - Math.abs(j - x);
                        sum += grid[i - h][x] + grid[i + h][x];
                    }
                    set.add(sum);
                }
            }
        }
        int size = Math.min(3, set.size());
        int[] res = new int[size];
        Iterator<Integer> iterator = set.iterator();
        for (int i = 0; i < size; i++) {
            res[i] = iterator.next();
        }
        return res;
    }

}

性能

目标

一个 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;
    }

}

性能