剑指offer专项突击版第4天

剑指 Offer II 010. 和为 k 的子数组
前缀和+哈希表+在线操作

class Solution {
    
public:
    int subarraySum(vector<int>& nums, int k) {
    
        int n = nums.size();
        unordered_map<int,int> um;
        int cnt = 0;
        um[0] = 1; //前缀和为0的个数，由于没有元素的话和为0，所以这里个数为1
        for(int i = 0,sum = 0; i < n; i++){
    
            sum += nums[i];
            if(um.count(sum-k) != 0) cnt += um[sum-k];
            um[sum] ++ ;
        }
        return cnt;
    }
};

剑指 Offer II 011. 0 和 1 个数相同的子数组
前缀和+哈希表

• $counter$ 记录当前多出来 $1$ 的个数。
• 只需要枚举 $i$ ，然后哈希表记录每个 $i$ 对应的 $counter$ 值。
• 然后计算的时候就找哈希表是否有这个$counter$值，如果有返回对应的下标（与当前下标做差即为 $1$ 和 $0$ 数量相同的连续子数组长度）。

class Solution {
    
public:
    int findMaxLength(vector<int>& nums) {
    
        int n = nums.size();
        unordered_map<int,int> um;
        int res = 0, counter = 0;
        um[counter] = -1;
        for(int i = 0; i < n; i++) {
    
            if(nums[i] == 1) counter++;
            else counter--;
            if(um.count(counter) != 0 ) {
    
                int preidx = um[counter];
                res = max(res,i-preidx);
            } else {
    
                um[counter] = i;
            }
        }
        return res;
    }
};

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

class Solution {
    
public:
    int pivotIndex(vector<int>& nums) {
    
        int total = 0;
        for(auto num : nums) total += num;
        for(int i = 0, sum = 0; i < nums.size(); i++) {
    
            if(total - sum - nums[i] == sum) return i;
            sum += nums[i];
        }
        return -1;
    }
};

剑指 Offer II 013. 二维子矩阵的和
经典二维前缀和

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