前缀和

剑指 Offer II 010. 和为 k 的子数组

  • 简单前缀和

    1. class Solution {
    2. public:
    3.   int subarraySum(vector<int>& nums, int k) {
    4.       int res = 0;
    5.       partial_sum(nums.begin(), nums.end(), nums.begin());
    6.       unordered_map<int,int> hash;
    7.       hash[0] = 1;
    8.       for(auto a : nums){
    9.           res+=hash[a-k];
    10.           hash[a]++;
    11.       }
    12.       return res;
    13.   }
    14. };

    剑指 Offer II 011. 0 和 1 个数相同的子数组

    由于「00 和 11 的数量相同」等价于「11 的数量减去 00 的数量等于 00」，我们可以将数组中的 00 视作 -1−1，则原问题转换成「求最长的连续子数组，其元素和为 00」。

  • hash[0]=-1，因为当前缀和为零时，代表前面所有的元素都是子集，应该是i+1的长度。

  • 使用一个tmp来进行0到-1的转换。
  • 使用哈希表来存储前缀和以及最小下标

  • 当哈希表中存在当前前缀和时，说明这一段的0和1数量相同，长度为i-hash[psum]

    1. class Solution {
    2. public:
    3.   int findMaxLength(vector<int>& nums) {
    4.       int psum = 0, maxlen = 0, n = nums.size();
    5.       unordered_map<int,int> hash;
    6.       hash[0] = -1;
    7.       for(int i = 0; i < n; i++){
    8.           int tmp = nums[i]==0? -1:1;
    9.           psum += tmp;
    10.           if(hash.count(psum)) {
    11.               maxlen = max(maxlen, i-hash[psum]);
    12.           } else {
    13.               hash[psum] = i;
    14.           }
    15.       }
    16.       return maxlen;
    17.   }
    18. };

    剑指 Offer II 012. 左右两边子数组的和相等

  • 注意判断边界条件

  • 根据2*psum[i-1]+nums[i] = total这个公式来确定

  • 尽量不要使用partial_sum来计算前缀和，直接在for循环里面累加就行了

    1. class Solution {
    2. public:
    3.   int pivotIndex(vector<int> &nums) {
    4.       int total = accumulate(nums.begin(), nums.end(), 0);
    5.       int sum = 0;
    6.       for (int i = 0; i < nums.size(); ++i) {
    7.           if (2 * sum + nums[i] == total) {
    8.               return i;
    9.           }
    10.           sum += nums[i];
    11.       }
    12.       return -1;
    13.   }
    14. };

    剑指 Offer II 013. 二维子矩阵的和

  • 前缀和矩阵

  • 先使用动态规划求矩阵的前缀和
  • 然后用前缀和然会子矩阵的和

  • 但是真的不能粗心大意

    1. class NumMatrix {
    2. private:
    3. vector<vector<int>> matrixsum;
    4. public:
    5.   NumMatrix(vector<vector<int>>& matrix) {
    6.       int n = matrix.size(), m = matrix[0].size();
    7.       vector<int> tmp(matrix[0].size()+1);
    8.       matrixsum.resize(matrix.size()+1, tmp);
    9.       for(int i = 1; i <= n; i++){
    10.           for(int j = 1; j <= m; j++){
    11.               matrixsum[i][j] = matrixsum[i-1][j]+matrixsum[i][j-1]-matrixsum[i-1][j-1]+matrix[i-1][j-1];
    12.           }
    13.       }
    14.   }
    16.   int sumRegion(int row1, int col1, int row2, int col2) {
    17.       return matrixsum[row2+1][col2+1] - matrixsum[row1][col2+1]-matrixsum[row2+1][col1]+matrixsum[row1][col1];
    18.   }
    19. };