【C++刷题】优选算法——前缀和

1. 【模板】前缀和

int main()
{
    int n, q;
    cin >> n >> q;
    vector<long long> v(n+1, 0);
    for(int i = 1; i <= n; ++i)
    {
        cin >> v[i];
        v[i] += v[i-1];
    }
    int l, r;
    while(cin >> l >> r)
    {
        cout << v[r] - v[l - 1] << endl;
    }
    return 0;
}

2. 【模板】二维前缀和

int main()
{
    int n, m, q; // n 行, m 列
    cin >> n >> m >> q;
    vector<vector<long long>> vv(n+1, vector<long long>(m+1, 0));
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= m; ++j)
        {
            cin >> vv[i][j];
            vv[i][j] += (vv[i - 1][j] + vv[i][j - 1] - vv[i - 1][j - 1]);
        }
    }
    int x1, y1, x2, y2;
    while(cin >> x1 >> y1 >> x2 >> y2)
    {
        cout << vv[x2][y2] - vv[x1-1][y2] - vv[x2][y1-1] + vv[x1-1][y1-1] << endl;
    }
    return 0;
}

3. 寻找数组的中心下标

int pivotIndex(vector<int>& nums)
{
    int n = nums.size();
    vector<int> dp(n);
    dp[0] = nums[0];
    for(int i = 1; i < n; ++i)
    {
        dp[i] = nums[i] + dp[i-1];
    }
    if(dp[n-1] - dp[0] == 0) return 0;
    for(int i = 1; i < n; ++i)
    {
        if(dp[i-1] == dp[n-1] - dp[i]) return i;
    }
    return -1;
}

4. 除自身以外数组的乘积

// 空间复杂度 - O(n)
vector<int> productExceptSelf(vector<int>& nums) 
{
    int n = nums.size();
    // f[i] - 表示 [0, i-1] 区间元素的乘积 -> f[i] = f[i-1] * nums[i-1];
    vector<int> f(n);
    // g[i] - 表示 [i+1, n-1] 区间元素的乘积 -> g[i] = g[i+1] * nums[i+1];
    vector<int> g(n);
    f[0] = 1;
    g[n-1] = 1;
    for(int i = 1; i < n; ++i)
    {
        f[i] = f[i-1] * nums[i-1];
    }
    for(int i = n-2; i >= 0; --i)
    {
        g[i] = g[i+1] * nums[i+1];
    }
    vector<int> ret(n);
    for(int i = 0; i < n; ++i)
    {
        ret[i] = f[i] * g[i];
    }
    return ret;
}

// 空间复杂度 - O(1)
vector<int> productExceptSelf(vector<int>& nums) 
{
    int n = nums.size();
    vector<int> dp(n);
    dp[0] = nums[0];
    for(int i = 1; i < n; ++i)
    {
        dp[i] = nums[i] * dp[i-1];
    }
    
    int right = 1;
    for(int i = n-1; i >= 1; --i)
    {
        dp[i] = dp[i-1] * right;
        right *= nums[i];
    }
    dp[0] = right;
    return dp;
}

5. 和为 K 的子数组

unordered_map<int, int> hash; // <前缀和, 次数>
int subarraySum(vector<int>& nums, int k)
{
    hash[0] = 1;

    int sum = 0, ret = 0;
    for(int e : nums)
    {
        sum += e; // 计算当前位置的前缀和
        if(hash.count(sum - k)) ret += hash[sum - k];
        hash[sum]++;
    }
    return ret;
}

6. 和可被 K 整除的子数组

// 1.同余定理: 如果 (a - b) / p = k ... 0 则推出 a % p = b % p
// 2.因为 负 % 正 = 负, 所以为兼顾取模结果的正负性, 使用 (a % p + p) % p 做修正
unordered_map<int, int> hash; // <前缀和sum的余数, 次数>
int subarraysDivByK(vector<int>& nums, int k)
{
    hash[0] = 1;

    int sum = 0, ret = 0;
    for(int e : nums)
    {
        sum += e;
        int r = (sum % k + k) % k; // 修正后的余数
        if(hash.count(r)) ret += hash[r];
        hash[r]++;
    }
    return ret;
}

7. 连续数组

// 转化：将所有的0改为-1, 转化为寻找和为0的最长子数组
unordered_map<int, int> hash; // <前缀和, 下标>
int findMaxLength(vector<int>& nums)
{
    for(int& e : nums) if(e == 0) e = -1;
    hash[0] = -1;

    int sum = 0, len = 0;
    for(int i = 0; i < nums.size(); ++i)
    {
        sum += nums[i];
        if(hash.count(sum)) len = max(len, i - hash[sum]);
        else hash[sum] = i;
    }
    return len;
}

8. 矩阵区域和

vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k)
{
    int m = mat.size(), n = mat[0].size();
    vector<vector<int>> dp(m+1, vector<int>(n+1));
    for(int i = 1; i <= m; ++i)
    {
        for(int j = 1; j <= n; ++j)
        {
            dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + mat[i-1][j-1];
        }
    }

    vector<vector<int>> answer(m, vector<int>(n));
    for(int i = 0; i < m; ++i)
    {
        for(int j = 0; j < n; ++j)
        {
            // 左上角 - [i-k, j-k]
            // 右下角 - [i+k, j+k]
            int top = max(0, i-k) + 1, left = max(0, j-k) + 1;
            int bottom = min(m-1, i+k) + 1, right = min(n-1, j+k) + 1;
            answer[i][j] = dp[bottom][right] - dp[bottom][left-1] - dp[top-1][right] + dp[top-1][left-1];
        }
    }
    return answer;
}