前缀和 - 《算法》

1. 前缀和定义
- 1.1 适用场景
2. 一维数组前缀和
3. 二维数组前缀和
4. 前缀和在字符串中问题中的应用
- 考试的最大困扰度">4.1 leetcode2024 考试的最大困扰度
- 每个数字的频率都相同的独特子字符串的数量">leetcode2168 每个数字的频率都相同的独特子字符串的数量
题目

1. 前缀和定义

对于一个给定数列A，它的前缀和数列preSum[i]定义为 前缀和 - 图1

1.1 适用场景

原始数组不会被修改，频繁查询某个区间的累加和

2. 一维数组前缀和

preSum = new int[nums.length+1];
for(int i = 1;i < preSum.length;i++) {
    preSum[i] = preSum[i-1] + nums[i-1];
}

preSum[i]代表nums[0...i-1]的累加和
这里前缀和数组比原数组长度大1的原因当需要求[i,j]范围的数组元素和时，如果i=0不需要特判，其值等于preSum[j+1] - preSum[i]

3. 二维数组前缀和

假设有一矩阵A，矩阵值如下所示：
1 2 4 3
5 1 2 4
6 3 5 9
定义一个矩阵preSum，前缀和 - 图2 ，从图上理解便是从从矩阵左上角(0,0)到(i,j)的所有元素累加和。这个累加和可以由比(i,j)坐标行数小1以及列数小1的两个前缀和求得
preSum[i][j] = preSum[i-1][j] + preSum[i][j-1] - preSum[i-1][j-1] + A[i-1][j-1]
由此可推导出若求左上角坐标为(x1,y1)，右上角坐标为(x2,y2)的矩阵内的值的总和，求和公式为：
preSum[x2+1][y2+1] - preSum[x1][y2+1] - preSum[x2+1][y1] + preSum[x1][y1]

public class NumMatrix {
    private int[][] preSum;
    public NumMatrix(int[][] matrix) {
        preSum = new int[matrix.length+1][];
        for(int i = 0;i < preSum.length;i++) {
            preSum = new int[matrix[0].length+1];
        }
        for(int i = 1;i < preSum.length;i++) {
            for(int j = 1;j < preSum[0].length;j++) {
                preSum[i][j] = preSum[i-1][j] + preSum[i][j-1] - preSum[i-1][j-1] + matrix[i-1][j-1];
            }
        }
    }
    public int sumRegion(int row1, int col1, int row2, int col2) {
        return preSum[row2+1][col2+1] - preSum[row1][col2+1] - preSum[row2+1][col1] + preSum[row1][col1];
    }
}

4. 前缀和在字符串中问题中的应用

通常字符串子串问题也有前缀和的应用

4.1 leetcode2024 考试的最大困扰度

一位老师正在出一场由 n 道判断题构成的考试，每道题的答案为 true （用 ‘T’ 表示）或者 false （用 ‘F’ 表示）。老师想增加学生对自己做出答案的不确定性，方法是 最大化 有 连续相同 结果的题数。（也就是连续出现 true 或者连续出现 false）。
给你一个字符串 answerKey ，其中 answerKey[i] 是第 i 个问题的正确结果。除此以外，还给你一个整数 k ，表示你能进行以下操作的最多次数：

每次操作中，将问题的正确答案改为 ‘T’ 或者 ‘F’ （也就是将 answerKey[i] 改为 ‘T’ 或者 ‘F’ ）。

请你返回在不超过 k 次操作的情况下，最大连续 ‘T’ 或者 ‘F’ 的数目。
示例 1：
输入：answerKey = “TTFF”, k = 2 输出：4 解释：我们可以将两个 ‘F’ 都变为 ‘T’ ，得到 answerKey = “TTTT“ 。总共有四个连续的 ‘T’ 。
示例 2：
输入：answerKey = “TFFT”, k = 1 输出：3 解释：我们可以将最前面的 ‘T’ 换成 ‘F’ ，得到 answerKey = “FFF_T” 。或者，我们可以将第二个 ‘T’ 换成 ‘F’ ，得到 answerKey = “TFFF“ 。两种情况下，都有三个连续的 ‘F’ 。
示例 3：
输入：answerKey = “TTFTTFTT”, k = 1 输出：5 解释：我们可以将第一个 ‘F’ 换成 ‘T’ ，得到 answerKey = “TTTTTFTT” 。或者我们可以将第二个 ‘F’ 换成 ‘T’ ，得到 answerKey = “TTFTTTTT_” 。两种情况下，都有五个连续的 ‘T’ 。

提示：

n == answerKey.length
1 <= n <= 5 * 10^4
answerKey[i] 要么是 ‘T’ ，要么是 ‘F’
1 <= k <= n

看到字符串的长度为10^4，O(n^2)时间复杂度必定会超时，应当考虑使用O(n)或O(logn)时间复杂度的算法解题，本地最佳解法应当是滑动窗口算法，时间复杂度为O(n)，但是看到网上还有一种使用前缀和加二分查找的解决办法，感觉挺好，特此记录下

public int maxConsecutiveAnswers(String answerKey, int k) {
        int[] pre = new int[answerKey.length() + 1];
        for(int i = 1;i <= answerKey.length();i++) {
            pre[i] = pre[i-1] + (answerKey.charAt(i-1) == 'T'?1:0);
        }
        int l = 1;
        int right = answerKey.length();
        int pos = -1;
        while (l <= right) {
            int mid  = l + (right-l) / 2;
            if(judge(mid,pre,k)) {
                pos = mid;
                l = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return pos;
    }
    boolean judge(int x,int[] pre,int k) {
        for(int i = x;i < pre.length;i++) {
            int tCount = pre[i] - pre[i-x];
            int wCount = x - tCount;
            if(Math.min(tCount,wCount) <= k) {
                return true;
            }
        }
        return false;
    }

public int maxConsecutiveAnswers(String answerKey, int k) {
        int left = 0;
        int right = 0;
        int tCount = 0;
        int res = -1;
        int pos = -1;
        while(right < answerKey.length()) {
            char c = answerKey.charAt(right);
            right++;
            if(c == 'T') {
                tCount++;
            }
            while(tCount > k && right - left - tCount > k) {
                if(answerKey.charAt(left++) == 'T') {
                    tCount--;
                }
            }
            res = Math.max(res,right - left);
        }
        return res;
    }

leetcode2168 每个数字的频率都相同的独特子字符串的数量

给你一个由数字组成的字符串 s，返回 _s 中独特子字符串数量，其中的每一个数字出现的频率都相同。_

示例1:
输入: s = “1212” 输出: 5 解释: 符合要求的子串有 “1”, “2”, “12”, “21”, “1212”. 要注意，尽管”12”在s中出现了两次，但在计数的时候只计算一次。
示例 2:
输入: s = “12321” 输出: 9 解释: 符合要求的子串有 “1”, “2”, “3”, “12”, “23”, “32”, “21”, “123”, “321”.

解释:

1 <= s.length <= 1000
s 只包含阿拉伯数字.

分析：若暴力法找出所有的子串，并看子串是否是独特的，那么时间复杂度为O(n^3)，肯定会超时，当看到子串中字符出现的次数时应该联想到前缀和解法，可以定义前缀和数组preSum[i][j]，其中0 <= j <= 9,代表以i结尾的子串中各个数字出现的次数，那么子串s[k…z]中各个10个数字（0、1、2、3、4、5、6、7、8、9）出现的次数便可以由preSum[z+1][j] - preSum[k][j]求出

public int equalDigitFrequency(String s) {
        int[][] preSum = new int[s.length()+1][];
        for(int i = 0;i < preSum.length;i++) {
            preSum[i] = new int[10];
        }
        for(int i = 1;i <= s.length();i++) {
            int tmp = s.charAt(i-1) - '0';
            preSum[i][tmp] += 1;
            for(int j = 0;j < 10;j++) {
                preSum[i][j] += preSum[i-1][j];
            }
        }
        Set<String> res = new HashSet<>();
        for(int i = 0;i < s.length();i++) {
            for(int j = i;j < s.length();j++) {
                if(check(i,j,preSum)) {
                    res.add(s.substring(i,j+1));
                }
            }
        }
        return res.size();
    }
    boolean check(int left,int right,int[][] preSum) {
        Set<Integer> diff = new HashSet<>();
        for(int i = 0;i < 10;i++) {
            int count = preSum[right+1][i] - preSum[left][i];
            if(count > 0) {
                diff.add(count);
            }
            if(diff.size() > 1) {
                return false;
            }
        }
        return true;
    }

题目

Leetcode303

给定一个整数数组 nums，处理以下类型的多个查询:

计算索引 left 和 right （包含 left 和 right）之间的 nums 元素的和，其中 left <= right
实现 NumArray 类：

NumArray(int[] nums) 使用数组 nums 初始化对象
int sumRange(int i, int j) 返回数组 nums 中索引 left 和 right 之间的元素的总和，包含 left 和 right 两点（也就是 nums[left] + nums[left + 1] + … + nums[right] )

示例 1：
输入：
[“NumArray”, “sumRange”, “sumRange”, “sumRange”]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
输出：
[null, 1, -1, -3]
解释：
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return 1 ((-2) + 0 + 3)
numArray.sumRange(2, 5); // return -1 (3 + (-5) + 2 + (-1))
numArray.sumRange(0, 5); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))

class NumArray {
    private int[] preSum;
    public NumArray(int[] nums) {
        preSum = new int[nums.length+1];
        for(int i = 1;i < preSum.length;i++) {
            preSum[i] = preSum[i-1] + nums[i-1];
        }
    }
    public int sumRange(int left, int right) {
       return preSum[right+1] - preSum[left];
    }
}

leetcode304

给定一个二维矩阵 matrix，以下类型的多个请求：

计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2) 。
实现 NumMatrix 类：
前缀和 - 图3

NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
int sumRegion(int row1, int col1, int row2, int col2) 返回左上角 (row1, col1) 、右下角 (row2, col2) 所描述的子矩阵的元素总和。

public class NumMatrix {
    private int[][] preSum;
    public NumMatrix(int[][] matrix) {
        preSum = new int[matrix.length+1][matrix[0].length+1];
        for(int i = 1;i < preSum.length;i++) {
            for(int j = 1;j < preSum[0].length;j++) {
                preSum[i][j] = preSum[i-1][j] + preSum[i][j-1] - preSum[i-1][j-1] + matrix[i-1][j-1];
            }
        }
    }
    public int sumRegion(int row1, int col1, int row2, int col2) {
        return preSum[row2+1][col2+1] - preSum[row1][col2+1] - preSum[row2+1][col1] + preSum[row1][col1];
    }
}