Skip to content

Latest commit

 

History

History
263 lines (227 loc) · 8.78 KB

专题 - 前缀和.md

File metadata and controls

263 lines (227 loc) · 8.78 KB
Raw

前缀和

目的: 快速求出数组中「连续」一段的和

注意prefixSum的下标错开一位, 从1开始

LC724. 寻找数组的中心下标

一维前缀和(错开一位), 然后找满足prefixSum[i]*2 == allSum - nums[i]的位置i

p.s. 这题的前缀和不错位更好写一些

搜索想到二分查找是好事...但这题也不是有序呀...

int pivotIndex(vector<int>& nums) {
    // 前缀和(错开一位)
    vector<int> prefixSum(nums.size()+1, 0);
    for(int i=1; i<=nums.size(); i++){
        prefixSum[i] = nums[i-1] + prefixSum[i-1];
    }
    // 找满足条件的下标 i
    for(int i=0; i<nums.size(); i++){
        // 也可以两边都把nums[i]包含进去
        if(prefixSum[i]*2 == prefixSum.back()-nums[i])
            return i;
    }
    return -1;
}

https://leetcode.cn/problems/find-pivot-index/

LC303. 区域和检索-数组不可变

标准的前缀和模板, 注意prefixSum下标和范围下标的对齐

vector<int> prefixSum;
NumArray(vector<int>& nums) {
    prefixSum.resize(nums.size()+1);
    fill(prefixSum.begin(), prefixSum.end(), 0);
    for(int i=1; i<=nums.size(); i++){
        prefixSum[i] = prefixSum[i-1]+nums[i-1];
    }
}

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

https://leetcode.cn/problems/range-sum-query-immutable/

LC560. 和为K的子数组

Keyword: 前缀和 map

nums[i]可能小于0, 因此不可以用双指针/滑动窗口

初始想法: 使用前缀和, 接下来计算区间和(枚举<起点,终点>) => 超时 ([12/23]🤪超时打卡+1)

枚举左、右两个端点超时 => 使用map记录已经出现的prefixSum[i]

  • 如果(左侧)已经有值为prefixSum[i]-k的前缀和, 如果有, 个数应为mp[prefixSum[i]-k]
  • 并且对每个prefixSum[i]计次, 即mp[prefixSum[i]]++
  • 不会重复计数, 因为每次为prefixSum[i]找值为prefixSum[i]-k的前缀和个数时, 都保持i为右边界

相似题目: 剑指offer50. 向下的路径节点之和

int subarraySum(vector<int>& nums, int k) {
    int n = nums.size();
    // 1. 求前缀和(错开一位也方便后面计算区间和)
    vector<int> prefixSum(n+1, 0);
    for(int i=1; i<=n; i++){
        prefixSum[i] = prefixSum[i-1] + nums[i-1];
    }
    // 2. 从左到右扩建map记录左边前缀和值的出现次数
    unordered_map<int, int> mp;
    mp[0] = 1;
    int ans = 0;
    for(int i=1; i<=n; i++){
        ans += mp[prefixSum[i]-k];
        mp[prefixSum[i]]++;
    }
    return ans;
}

https://leetcode.cn/problems/subarray-sum-equals-k

二维前缀和

sum[x1:x2][y1:y2] = sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1]

初始化

  • Row 0 & Col 0: 一维前缀和
  • sum[i][j] = nums[i][j] + sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1]
304. 二维区域和检索-矩阵不可变

标准的二维前缀和模板, 注意将前缀和数组下标与范围下标对齐

class NumMatrix {
public:
    vector<vector<int>> preSum;
    NumMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        vector<vector<int>> prefixSum(m+1, vector(n+1, 0));
        for(int i=1; i<=m; i++){
            for(int j=1; j<=n; j++){
                prefixSum[i][j] = prefixSum[i-1][j]+prefixSum[i][j-1]-prefixSum[i-1][j-1] + matrix[i-1][j-1];
            }
        }
        preSum = prefixSum;
    }
    int sumRegion(int x1, int y1, int x2, int y2) {
        x1++;   y1++;   x2++;   y2++;
        return preSum[x2][y2]-preSum[x1-1][y2]-preSum[x2][y1-1]+preSum[x1-1][y1-1];
    }
};

https://leetcode.cn/problems/range-sum-query-2d-immutable/

LC1314. 矩阵区域和

对于每一个(i, j)求prefixSum[i-k:i+k][j-k:j+k], 注意判断下标越界

vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
    int m = mat.size();
    int n = mat[0].size();
    // 构造前缀和
    vector<vector<int>> prefixSum(m+1, vector<int>(n+1, 0));
    for(int i=1; i<=m; i++){
        for(int j=1; j<=n; j++){
            prefixSum[i][j] = prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1] + mat[i-1][j-1];
        }
    }
    // 枚举中心位置
    for(int i=1; i<=m; i++){
        for(int j=1; j<=n; j++){
            int x1 = (i-k<1) ? 1 : i-k;
            int y1 = (j-k<1) ? 1 : j-k;
            int x2 = (i+k>m) ? m : i+k;
            int y2 = (j+k>n) ? n : j+k;
            mat[i-1][j-1] = prefixSum[x2][y2] - prefixSum[x1-1][y2] - prefixSum[x2][y1-1] + prefixSum[x1-1][y1-1];
        }
    }
    return mat;
}

https://leetcode.cn/problems/matrix-block-sum/

计数前缀和

LC2483. 商店的最少代价: 1️⃣➕1️⃣双周赛第三题

  • 计数前缀和: 对左边出现过的所有N(或者Y)计数

  • 枚举分界点, 求左侧N的个数 + 右侧Y的个数作为cost

int bestClosingTime(string customers) {
    // nCnt[i]: 统计 0~i 中'N'的个数
    int n = customers.size();
    vector<int> nCnt(n+1);  // 前缀和数组
    nCnt[0] = 0;
    for(int i=1; i<=n; i++){
        nCnt[i] = nCnt[i-1] + (customers[i-1]=='N');
    }
    int ans = 0;
    int minCost = n;
    for(int i=0; i<=n; i++){
        // cost: 从 i 位置截断(注意nCnt[]是从下标1开始存储的)
        //   - 前面'N'的个数 => nCnt[N]
        //   - 后面'Y'的个数 => n-i-(nCnt[n]-nCnt[i])   // 括号里的部分(nCnt[n]-nCnt[i]), 前缀和的思想
        int cost = nCnt[i] + (n - i - nCnt[n] +nCnt[i]);
        if(cost < minCost){
            minCost = cost;
            ans = i;
        }
    }
    return ans;
}

https://leetcode.cn/problems/minimum-penalty-for-a-shop/

剑指offer50. 向下的路径节点之和

求一段路径的总和, 很像前缀和, 不过本题更在意当前路径上已经存在几个x-target, 而不注重在路径上的具体位置

于是就变成了「树状」的LC560. 和为K的子数组

初始化一个mp[0]=1, 表示空树

backtrack(root, sum, target):

  • 将root->val加入sum
  • 如果当前DFS路径上已经存在x-target, ans += mp[sum-target]
  • 记录当前路径上的前缀和, mp[sum]++
  • 递归左右子树
  • 递归左右子树后要取消对sum的计数, mp[sum]--

⚠️注意路径和可能发生int溢出

unordered_map<long long, int> mp;   // 在当前路径上, 记录从root到cur上的pathSum出现的次数
int ans = 0;
void backtrack(TreeNode* root, long long pathSum, int targetSum){
    if(root==NULL)
        return ;
    pathSum += root->val;
    // 前缀和, 应该是pathSum - x = targetSum
    ans += mp[pathSum-targetSum];
    mp[pathSum]++;
    backtrack(root->left, pathSum, targetSum);
    backtrack(root->right, pathSum, targetSum);
    mp[pathSum]--;
}
int pathSum(TreeNode* root, int targetSum) {
    // ! 和LC560一样， 别忘了mp[0]=1
    mp[0] = 1;
    backtrack(root, 0, targetSum);
    return ans;
}

https://leetcode.cn/problems/6eUYwP/

LC2559. 统计范围内的元音字符串数: 周赛331第二题

注意读题, 以aeiou开头或结尾的单词, 不是包含aeiou

unordered_set<char> st = {'a','e','i','o','u'};
bool check(string word){
    if(st.find(word[0])==st.end())
        return false;
    if(st.find(word.back())==st.end())
        return false;
    return true;
}
vector<int> vowelStrings(vector<string>& words, vector<vector<int>>& queries) {
    int n = words.size();
    vector<int> prefixSum(n+1, 0);
    for(int i=1; i<=n; i++){
        prefixSum[i] = prefixSum[i-1] + (check(words[i-1])==true);
        cout<<prefixSum[i]<<" ";
    }
    int m = queries.size();
    vector<int> ans(m, 0);
    for(int i=0; i<m; i++){
        ans[i] = prefixSum[queries[i][1]+1] - prefixSum[queries[i][0]];
    }
    return ans;
}

https://leetcode.cn/problems/count-vowel-strings-in-ranges/