08 区域和检索 前缀和

​ 一维的前缀和，二维的积分图，都是把每个位置之前的一维线段或二维矩形预先存储，方便加速计算。如果需要对前缀和或积分图的值做寻址，则要存在哈希表里；如果要对每个位置记录前缀和或积分图的值，则可以储存到一维或二维数组里，也常常伴随着动态规划。

303 区域和检索 (opens new window)

设计一个类，使得其能够快速查询给定整数数组 nums中，求数组从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j两点。

NumArray 类的调用样例：

输入：["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))

解析：

​ 对于一维的数组，我们可以使用前缀和来解决此类问题。先建立一个与数组 nums 长度相同的新数组 psum，表示 nums 每个位置之前前所有数字的和。psum 数组可以通过 C++ 自带的 partial_sum 函数建立，也可以直接遍历一遍 nums 数组，并利用状态转移方程 psum[i] = psum[i-1] + nums[i] 完成统计。如果我们需要获得位置 i 和 j 之间的数字和，只需计算 psum[j+1] - psum[i] 即可。

class NumArray {
    vector<int> psum;
public:
    NumArray(vector<int>& nums) {
        psum.resize(nums.size()+1);
        partial_sum(nums.begin(),nums.end(),psum.begin()+1);
    }
    
    int sumRange(int left, int right) {
        return psum[right+1]-psum[left];
    }
};

304 二维区域和检索 (opens new window)

设计一个类，使得其能够快速查询给定矩阵中，任意两个位置包围的长方形中所有数字的和。计算其子矩形范围内元素的总和，该子矩阵的 左上角 为 (row1, col1) ，右下角 为 (row2, col2) 。

NumMatrix 类的调用样例。其中 sumRegion 函数的四个输入分别是第一个点的横、纵坐标，和第二个点的横、纵坐标。

输入: ["NumMatrix","sumRegion","sumRegion","sumRegion"] [[[[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]]],[2,1,4,3],[1,1,2,2],[1,2,2,4]]

输出: [null, 8, 11, 12]

解释: NumMatrix numMatrix = new NumMatrix([[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]]]); numMatrix.sumRegion(2, 1, 4, 3); // return 8 (红色矩形框的元素总和) numMatrix.sumRegion(1, 1, 2, 2); // return 11 (绿色矩形框的元素总和) numMatrix.sumRegion(1, 2, 2, 4); // return 12 (蓝色矩形框的元素总和)

解析：

​ 类似于前缀和，我们可以把这种思想拓展到二维，即积分图（image integral）。我们可以先建立一个 intergral 矩阵，intergral[i][j] 表示以位置 (0, 0) 为左上角、位置 (i, j) 为右下角的长方形中所有数字的和。 ​ 如下图所示，我们可以用动态规划来计算 integral 矩阵：intergral[i][j] = matrix[i-1][j-1] + integral[i-1][j] + integral[i][j-1] - integral[i-1][j-1]，即当前坐标的数字 + 上面长方形的数字和 + 左边长方形的数字和 - 上面长方形和左边长方形重合面积（即左上一格的长方形）中的数字和。

​ 如下图所示，假设我们要查询长方形 E 的数字和，因为 E = D − B − C + A，我们发现 E 其实可以由四个位置的积分图结果进行加减运算得到。因此这个算法在预处理时的时间复杂度为 O(mn)，而在查询时的时间复杂度仅为 O(1)。

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

307. 区域和检索 - 数组可修改 (opens new window)

线段树求解

560 和为 K 的子数组 (opens new window)

给定一个数组，寻找和为 k 的连续区间个数。

输入一个一维整数数组和一个整数值 k；输出一个整数，表示满足条件的连续区间个数。

输入：nums = [1,2,3], k = 3
输出：2

解析：

​ 本题同样是利用前缀和，不同的是这里我们使用一个哈希表 hashmap，其键是前缀和，而值是该前缀和出现的次数。在我们遍历到位置 i 时，假设当前的前缀和是 psum，那么 hashmap[psum-k] 即为以当前位置结尾、满足条件的区间个数。

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        unordered_map<int,int> hash;
        int psum = 0;
        hash[0] = 1; // 初始情况
        int ans = 0;
        for(auto num: nums){
            psum += num;
            ans += hash[psum-k];
            ++hash[psum];
        }
        return ans;
    }
};

724 寻找数组的中心下标 (opens new window)

给定一个整数数组 nums ，请计算数组的 中心下标 。

数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。

输入：nums = [1, 7, 3, 6, 5, 6]
输出：3
解释：中心下标是 3 。
左侧数之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ，
右侧数之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ，二者相等。

解析：

方法一

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int n = nums.size();
        vector<int> L(n);
        for(int i=1;i<n;++i){
            L[i] = L[i-1] + nums[i-1];
        }
        vector<int> R(n);
        for(int i=n-2;i>=0;--i){
            R[i] = R[i+1] + nums[i+1];
        }
        for(int i=0;i<n;++i){
            if(L[i]==R[i]){
                return i;
            }
        }
        return -1;
    }
};

方法二

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        // 计算数组和
        int total = accumulate(nums.begin(),nums.end(),0);
        int sum = 0;
        for(int i=0;i<nums.size();++i){
            if(2*sum+nums[i]==total){ // 当前前缀和的两倍+当前值 == 数组和 那么当前位置为中心下标
                return i;
            }
            sum += nums[i];
        }
        return -1;
    }
};

238 除自身以外数组的乘积 (opens new window)

给定一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums 之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

解析：

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> LP(n), RP(n);
        // 记录所有元素的左侧累积
        LP[0] = 1;
        for(int i=1;i<n;++i){
            LP[i] = nums[i-1]*LP[i-1];
        }
        // 记录所有元素的右侧累积
        RP[n-1] = 1;
        for(int i=n-2;i>=0;--i){
            RP[i] = nums[i+1]*RP[i+1];
        }

        // 左右累积相乘得到除自身之外的累积
        vector<int> ans;
        for(int i=0;i<n;++i){
            ans.push_back(LP[i]*RP[i]);
        }
        return ans;
    }
};