LeetCode 前缀和问题

柔情只为你懂 2022-10-17 01:54 185阅读 0赞

# 一维前缀和 #

## 连续子数组和问题 ##

很多连续子数组问题都可以使用一维前缀和进行解决。

给定一个数组和目标值，求连续子数组的和等于目标值的个数。

*  数组中的值都大于0  
    这种题就比较简单，可以使用双指针来判断。

def solve(nums, target):
        n = len(nums)
        if n == 0:
            return 0
        if target == 0: #如果都为正数，不可能和为0
            return 0
        l, r = 0,0 # 左右指针
        ans = 0
        summ = 0
        while l < n and r < n:
            summ += nums[r] 
            r += 1
            while summ >= target:
                if summ == target:
                    ans += 1在这里插入代码片
                summ -= nums[l]
                l += 1
        return ans

### [560. 和为K的子数组][560. _K] ###

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。

示例 1 :

> 输入:nums = \[1,1,1\], k = 2  
> 输出: 2 , \[1,1\] 与 \[1,1\] 为两种不同的情况。

*  暴力（三次循环O(n^3）、必超时）
 *  暴力（二次循环O(n^2））

int solve(vector<int> &nums, int k){
        
        int n = nums.size();
        int res = 0;
        for(int i=0; i<n; ++i){
        
            int sum = 0;
            for(int j=i; j<n; ++j){
        
                sum += nums[j];
                if(sum == k){
        
                    res += 1;
                }
            }
            
        }
        return res;
    }

*  **前缀和**（简单O(n^2））  
    举个例子 nums = \[1,1,2,1,1\]，前缀和为 preSum = \[0（代表第-1下标）,1,2,4,5,5\]  
    那么我们可以知道 nums\[0,…,2\] = preSum\[2\]-preSum\[-1\] = 4 - 0 = 4  
    因此可以先保存一下前缀和，然后再判断是否为target
    
        int solve(vector<int> &nums, int k){
              
           int n = nums.size();
           vector<int> preSum(n+1, 0);
           int res = 0;
           preSum[0] = 0;
           for(int i=1; i<=n; ++i){
              
               preSum[i] = preSum[i-1] + nums[i-1];
           }
           for(int i=1; i<=n; ++i){
              
               for(int j=0; j<i; ++j){
              
                   if(preSum[i] - preSum[j] == k){
              
                       res++;
                   }
               }
           }
           return res;
        }
 *  **前缀和+哈希表**  
    我们知道连续子序列 \[ j , . . . . i \] \[j,....i\] \[j,....i\] 和等于 target的情况为  p r e S u m \[ i \] − p r e S u m \[ j − 1 \] = = t a r g e t preSum\[i\] - preSum\[j-1\] == target preSum\[i\]−preSum\[j−1\]==target ，即  p r e S u m \[ j − 1 \] = = p r e S u m \[ i \] − t a r g e t preSum\[j-1\] == preSum\[i\] - target preSum\[j−1\]==preSum\[i\]−target 因此我们在计算第i个前缀和时，我们可以统计之前前缀和等于 p r e S u m \[ i \] − t a r g e t preSum\[i\] - target preSum\[i\]−target的值有多少个。统计之前数存在多少我们可以使用哈希表。
    
        int solve(vector<int>& nums, int k) {
              
            int res = 0;
            int n = nums.size();
            unordered_map<int,int> hash;
            hash[0]++;
            int preSum=0;
            for(int i=1; i<=n; ++i){
              
                preSum += nums[i-1];
                auto find = hash.find(preSum - k);
                if(find != hash.end()){
              
                    res += find->second; 
                }
                hash[preSum]++;
            }
            return res;
        }

### [1248. 统计「优美子数组」][1248.] ###

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

如果某个 连续 子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。

请返回这个数组中「优美子数组」的数目。

示例 1：

> 输入：nums = \[1,1,2,1,1\], k = 3  
> 输出：2  
> 解释：包含 3 个奇数的子数组是 \[1,1,2,1\] 和 \[1,2,1,1\] 。

示例 2：

> 输入：nums = \[2,4,6\], k = 1  
> 输出：0  
> 解释：数列中不包含任何奇数，所以不存在优美子数组。

示例 3：

> 输入：nums = \[2,2,2,1,2,2,1,2,2,2\], k = 2  
> 输出：16

*  **前缀和 + 哈希表**

int numberOfSubarrays(vector<int>& nums, int k) {
        
            int n = nums.size();
            unordered_map<int, int> hash;
            hash[0]++;
            // 计算前序和
            int res = 0;
            int preOdd = 0;
            for(int i=1; i<=n; ++i){
        
                if(nums[i-1] % 2 == 1){
        
                    preOdd = preOdd + 1; 
                    hash[preOdd]++;
                }
                else{
        
                    preOdd = preOdd;
                    hash[preOdd]++;
                }
                auto find = hash.find(preOdd-k);
                if(find != hash.end()){
        
                    res += find->second;
                }
            }
            return res;
        }

*  **滑动窗口**

int numberOfSubarrays(vector<int>& nums, int k) {
        
        int n = nums.size();
        int l = 0, r = 0; 
        int cntOdd = 0, res = 0;
        while(r < n){
        
            if(nums[r++] % 2 == 1){
        
                cntOdd++;
            }
            if(cntOdd == k){
        
                int tmp = r;
                while(tmp < n && nums[tmp] % 2 == 0){
        
                    tmp++;
                }
                int rightCnt = tmp - r;
                int leftCnt = 0;
                while(nums[l] % 2 == 0){
        
                    l++;
                    leftCnt++;
                }
                res += (leftCnt+1) * (rightCnt+1);
                l++;
                cntOdd--;
            }
        }
        return res;
    }

### [209. 长度最小的子数组][209.] ###

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 \[numsl, numsl+1, …, numsr-1, numsr\] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：

> 输入：target = 7, nums = \[2,3,1,2,4,3\]  
> 输出：2  
> 解释：子数组 \[4,3\] 是该条件下的长度最小的子数组。

示例 2：

> 输入：target = 4, nums = \[1,4,4\]  
> 输出：1

示例 3：

> 输入：target = 11, nums = \[1,1,1,1,1,1,1,1\]  
> 输出：0

*  暴力（O(n^2) 超时)

int minSubArrayLen(int target, vector<int>& nums) {
        
       int res = INT_MAX;
       for(int i=0; i<nums.size(); ++i){
        
           int sum = 0;
           for(int j=i; j<nums.size(); ++j){
        
               sum += nums[j];
               if(sum >= target){
        
                   res = min(j - i + 1, res);
               }
           }
       }
       return res == INT_MAX ? 0 : res;
    }

*  **前缀表+二分搜索（O(nlogn))**

class Solution {
        
    public:
        int minSubArrayLen(int target, vector<int>& nums) {
        
            // 前缀和+二分
            int n = nums.size();
            int res = INT_MAX;
            vector<int> preSum(n+1, 0);
            preSum[0] = 0;
            for(int i=1; i<=n; ++i){
        
                preSum[i] = preSum[i-1] + nums[i-1];
            }
            for(int i=1; i<=n; ++i){
        
                int k = preSum[i] - target;
                if(k < 0){
        
                    continue;
                }
                else if(k == 0){
        
                    res = min(res, i);
                }
                else if(k > 0){
        
                    int l = 0, r = i-1;
                    while(l <= r){
        
                        int mid = l + (r - l)/2;
                        if(preSum[mid] == k){
        
                            res = min(i-mid, res);
                            break;
                        }else if(preSum[mid] > k){
        
                            r = mid-1;
                        }else if(preSum[mid] < k){
        
                            l = mid+1;
                            res = min(i-mid, res);
                        }
                    }
                }
            }
            return res== INT_MAX ? 0 : res;
        }
    };

*  **双指针（O(n))**

class Solution {
        
    public:
        int minSubArrayLen(int target, vector<int>& nums) {
        
            int res = INT_MAX;
            int l=0, r=0;
            int sum = 0;
            for(; r<nums.size(); r++){
        
                sum += nums[r];
                while(sum >= target){
        
                    res = min(res, r-l+1);
                    sum -= nums[l++];
                }
            }
            return res == INT_MAX ? 0 : res;
        }
    };

### [523. 连续的子数组和][523.] ###

给你一个整数数组 nums 和一个整数 k ，编写一个函数来判断该数组是否含有同时满足下述条件的连续子数组：

*  子数组大小 至少为 2 ，且
 *  子数组元素总和为 k 的倍数。

如果存在，返回 true ；否则，返回 false 。

如果存在一个整数 n ，令整数 x 符合 x = n \* k ，则称 x 是 k 的一个倍数。

示例 1：

> 输入：nums = \[23,2,4,6,7\], k = 6  
> 输出：true  
> 解释：\[2,4\] 是一个大小为 2 的子数组，并且和为 6 。

这里我们需要知道一个定理：  
**同余定理**： i % k − j % k = ( i − j ) % k i\\%k-j\\%k = (i-j)\\%k i%k−j%k=(i−j)%k

这种题一看就知道是前缀和，看到数据量1 <= nums.length <= 10^5，就知道仅用前缀和这种O(n^2)的算法会超时，因此想到哈希表，而题目还有一个条件是子数组大小至少为2，因此我们需要用哈希表保存下标。

class Solution {
        
    public:
        // 同余定理：i%k-j%k = (i-j)%k，所以 i%k == j%k
        bool checkSubarraySum(vector<int>& nums, int k) {
        
            vector<int> preSum = {
        0};
            for(int i=0; i<nums.size(); ++i){
        
                preSum.push_back(preSum[i] + nums[i]);
                if(i > 0 && preSum[i+1] % k == 0) return true;
            }
            unordered_map<int, int> hash;
            for(int i=1; i<preSum.size(); ++i){
        
                auto it = hash.find(preSum[i]%k);
                if(it == hash.end()){
        
                    hash[preSum[i]%k] = i; // 保存下标
                }else{
        
                    if(i - hash[preSum[i]%k] > 1) // 子数组大小至少为2
                        return true;
                }
            }  
            return false;
        }
    };

# 二维前缀和问题 #

二维前缀和问题一般与二维矩阵中的子矩阵相关。

### [304. 二维区域和检索 - 矩阵不可变][304. _ -] ###

给定一个二维矩阵，计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2) 。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2thcnJ5X3p6ag_size_16_color_FFFFFF_t_70]

上图子矩阵左上角 (row1, col1) = (2, 1) ，右下角(row2, col2) = (4, 3)，该子矩形内元素的总和为 8。

示例：

> 给定 matrix = \[  
> \[3, 0, 1, 4, 2\],  
> \[5, 6, 3, 2, 1\],  
> \[1, 2, 0, 1, 5\],  
> \[4, 1, 0, 1, 7\],  
> \[1, 0, 3, 0, 5\]  
> \]  
> sumRegion(2, 1, 4, 3) -> 8  
> sumRegion(1, 1, 2, 2) -> 11  
> sumRegion(1, 2, 2, 4) -> 12

**二维前缀和**解决的是二维矩阵中的矩形区域求和问题。

我们发现二维前缀和数组中的每一个格子记录的是以当前位置为区域的右下角（区域左上角恒定为原数组的左上角）的区域和

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2thcnJ5X3p6ag_size_16_color_FFFFFF_t_70 1]  
因此当我们要求 (x1, y1) 作为左上角，(x2, y2) 作为右下角 的区域和的时候，可以直接利用前缀和数组快速求解：

f \[ x 2 \] \[ y 2 \] − f \[ x 1 − 1 \] \[ y 2 \] − f \[ x 2 \] \[ y 1 − 1 \] + f \[ x 1 − 1 \] \[ y 1 − 1 \] f\[x2\]\[y2\] - f\[x1 - 1\]\[y2\] - f\[x2\]\[y1 - 1\] + f\[x1 - 1\]\[y1 - 1\] f\[x2\]\[y2\]−f\[x1−1\]\[y2\]−f\[x2\]\[y1−1\]\+f\[x1−1\]\[y1−1\]

class NumMatrix {
        
    public:
        vector<vector<int>> f;
        NumMatrix(vector<vector<int>>& matrix) {
        
            int n = matrix.size(), m = matrix[0].size();    
            f.resize(n+1, vector<int>(m+1));
            for(int i=1; i<=n; ++i){
        
                for(int j=1; j<=m; ++j){
        
                    // f(i, j) = f(i-1, j) + f(i, j-1) - f(i-1, j-1) + matrix[i-1][j-1];
                    if(i-1 == 0 && j-1 == 0){
        
                        f[1][1] = matrix[0][0];
                    }
                    else if(i-1 == 0){
        
                        f[i][j] = f[i][j-1] + matrix[i-1][j-1];
                    }
                    else if(j-1 == 0){
        
                        f[i][j] = f[i-1][j] + matrix[i-1][j-1];
                    }else if(i > 1 && j > 1){
        
                        f[i][j] = f[i-1][j] + f[i][j-1] - f[i-1][j-1] + matrix[i-1][j-1];
                    }
                }
            }
        }
        
        int sumRegion(int row1, int col1, int row2, int col2) {
        
            return f[row2+1][col2+1] - f[row2+1][col1] - f[row1][col2+1] + f[row1][col1];
        }
    };

### [363. 矩形区域不超过 K 的最大数值和][363. _ K] ###

给你一个 m x n 的矩阵 matrix 和一个整数 k ，找出并返回矩阵内部矩形区域的不超过 k 的最大数值和。

题目数据保证总会存在一个数值和不超过 k 的矩形区域。

示例 1：  
![在这里插入图片描述][20210529200950643.png]

> 输入：matrix = \[\[1,0,1\],\[0,-2,3\]\], k = 2  
> 输出：2  
> 解释：蓝色边框圈出来的矩形区域 \[\[0, 1\], \[-2, 3\]\] 的数值和是 2，且 2 是不超过 k 的最大数字（k = 2）。

示例 2：

> 输入：matrix = \[\[2,2,-1\]\], k = 3  
> 输出：3

这题和上一题类似，先把前缀和求出来，然后求最大值。

class Solution {
        
    public:
        int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
        
            int n = matrix.size(), m = matrix[0].size();    
            vector<vector<int>> f(n+1, vector<int>(m+1));
            for(int i=1; i<=n; ++i){
        
                for(int j=1; j<=m; ++j){
        
                    // f(i, j) = f(i-1, j) + f(i, j-1) - f(i-1, j-1) + matrix[i-1][j-1];
                    if(i-1 == 0 && j-1 == 0){
        
                        f[1][1] = matrix[0][0];
                    }
                    else if(i-1 == 0){
        
                        f[i][j] = f[i][j-1] + matrix[i-1][j-1];
                    }
                    else if(j-1 == 0){
        
                        f[i][j] = f[i-1][j] + matrix[i-1][j-1];
                    }else if(i > 1 && j > 1){
        
                        f[i][j] = f[i-1][j] + f[i][j-1] - f[i-1][j-1] + matrix[i-1][j-1];
                    }
                }
            }
            int res = INT_MIN;
            for(int row1=0; row1<n; ++row1){
        
                for(int col1=0; col1<m; ++col1){
        
                    for(int row2=row1; row2<n; ++row2){
        
                        for(int col2=col1; col2<m; ++col2){
        
                            int summ = f[row2+1][col2+1] - f[row2+1][col1] - f[row1][col2+1] + f[row1][col1];
                            if(summ <= k){
        
                                res = max(summ, res);
                            }
                        }
                    }
                }
            }
            return res;
        }
    };

### [1074. 元素和为目标值的子矩阵数量][1074.] ###

给出矩阵 matrix 和目标值 target，返回元素总和等于目标值的非空子矩阵的数量。

子矩阵 x1, y1, x2, y2 是满足 x1 <= x <= x2 且 y1 <= y <= y2 的所有单元 matrix\[x\]\[y\] 的集合。

如果 (x1, y1, x2, y2) 和 (x1’, y1’, x2’, y2’) 两个子矩阵中部分坐标不同（如：x1 != x1’），那么这两个子矩阵也不同。

示例 1：

> 输入：matrix = \[\[0,1,0\],\[1,1,1\],\[0,1,0\]\], target = 0  
> 输出：4  
> 解释：四个只含 0 的 1x1 子矩阵。

示例 2：

> 输入：matrix = \[\[1,-1\],\[-1,1\]\], target = 0  
> 输出：5  
> 解释：两个 1x2 子矩阵，加上两个 2x1 子矩阵，再加上一个 2x2 子矩阵。

### [1738. 找出第 K 大的异或坐标值][1738. _ K] ###

给你一个二维矩阵 matrix 和一个整数 k ，矩阵大小为 m x n 由非负整数组成。

矩阵中坐标 (a, b) 的 值 可由对所有满足 0 <= i <= a < m 且 0 <= j <= b < n 的元素 matrix\[i\]\[j\]（下标从 0 开始计数）执行异或运算得到。

请你找出 matrix 的所有坐标中第 k 大的值（k 的值从 1 开始计数）。

示例 1：

> 输入：matrix = \[\[5,2\],\[1,6\]\], k = 1  
> 输出：7  
> 解释：坐标 (0,1) 的值是 5 XOR 2 = 7 ，为最大的值。

示例 2：

> 输入：matrix = \[\[5,2\],\[1,6\]\], k = 2  
> 输出：5  
> 解释：坐标 (0,0) 的值是 5 = 5 ，为第 2 大的值。

因为矩阵中坐标 (a, b) 的 值 可由对所有满足 0 <= i <= a < m 且 0 <= j <= b < n 的元素 matrix\[i\]\[j\]执行异或运算得到。所以很容易想到前缀和问题。

很容易推出 f\[i\]\[j\] = f\[i-1\]\[j\] ^ f\[i\]\[j-1\] ^ f\[i-1\]\[j-1\] ^ matrix\[i-1\]\[j-1\];

而我们希望得到第k大的值，因此我们很容易想到最小堆，先存k个元素到最小堆中，然后把接下来求得的新值依次与堆顶元素进行比较，如果大则取出堆顶元素并插入到堆中。最后堆顶元素便是第k大元素。

class Solution {
        
    public:
        vector<vector<int>> f;
        int kthLargestValue(vector<vector<int>>& matrix, int k) {
        
            int m = matrix.size();
            int n = matrix[0].size();
            f.resize(m+1, vector<int>(n+1));
            int cnt = 0;
            priority_queue<int, vector<int>, greater<int>> pq;
            for(int i=1; i<=m; ++i){
        
                for(int j=1; j<=n; ++j){
        
                    if(i == 1 && j == 1) f[1][1] = matrix[0][0];
                    else if(i == 1) f[i][j] = f[i][j-1] ^ matrix[i-1][j-1];
                    else if(j == 1) f[i][j] = f[i-1][j] ^ matrix[i-1][j-1];
                    else f[i][j] = f[i-1][j] ^ f[i][j-1] ^ f[i-1][j-1] ^ matrix[i-1][j-1];
                    if(cnt < k){
        
                        pq.push(f[i][j]);
                        cnt++;
                    }
                    else{
        
                        if(f[i][j]>pq.top()){
        
                            pq.pop();
                            pq.push(f[i][j]);
                        }
                    }
                }
            }
            return pq.top();
        }
    };

[560. _K]: https://leetcode-cn.com/problems/subarray-sum-equals-k/
[1248.]: https://leetcode-cn.com/problems/count-number-of-nice-subarrays/
[209.]: https://leetcode-cn.com/problems/minimum-size-subarray-sum/
[523.]: https://leetcode-cn.com/problems/continuous-subarray-sum/
[304. _ -]: https://leetcode-cn.com/problems/range-sum-query-2d-immutable/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2thcnJ5X3p6ag_size_16_color_FFFFFF_t_70]: /images/20221014/5dd2388daa3a4dec9d1b41c4053435e1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2thcnJ5X3p6ag_size_16_color_FFFFFF_t_70 1]: /images/20221014/c791ad5615644e59b586b76212991338.png
[363. _ K]: https://leetcode-cn.com/problems/max-sum-of-rectangle-no-larger-than-k/
[20210529200950643.png]: /images/20221014/12580309338542b092ded3a94848ef4a.png
[1074.]: https://leetcode-cn.com/problems/number-of-submatrices-that-sum-to-target/
[1738. _ K]: https://leetcode-cn.com/problems/find-kth-largest-xor-coordinate-value/