算法

前缀和题目总结

前缀和

Posted by WenlSun" on July 26, 2020

和为k的子数组(中等)

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。和为0的只是和为k的特殊情况。和为k的子数组

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

class Solution {
   public:
    /**
     * 前缀和
     * 时间复杂度：O(n^2)
     * 空间复杂度：O(n)
     */
    int subarraySum(vector<int>& nums, int k) {
        if (!nums.size()) return 0;
        int n = nums.size();
        vector<int> pre(n + 1);
        for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + nums[i - 1];
        int res = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j <= n; j++) {
                if (pre[j] - pre[i] == k) res++;
            }
        }
        return res;
    }

    /**
     * 前缀和 + 哈希表
     * 时间复杂度：O(n)
     * 空间复杂度：O(n)
     * sum[j] - sum[i] = k --> sum[i] = sum[j]- k,即变为去找sum[i]出现的次数。
     */
    int subarraySum(vector<int>& nums, int k) {
        if (!nums.size()) return 0;
        unordered_map<int, int> hash;
        hash[0] = 1;
        int pre = 0, res = 0;
        for (auto n : nums) {
            pre += n;
            if (hash.count(pre - k)) res += hash[pre - k];
            hash[pre]++;
        }
        return res;
    }
};

最近接零的子数组和(绝对值最小的子数组)

给定一个整数数组，找到一个和最接近于零的子数组。返回满足要求的子数组的起始位置和结束位置。给出[-3, 1, 1, -3, 5]，返回[0, 2]，[1, 3]， [1, 1]， [2, 2] 或者[0, 4]

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

class Solution {
   public:
    typedef pair<int, int> PII;
    /**
     * 前缀和
     * 时间复杂度：O(n^2)
     * 空间复杂度：O(n)
     */
    vector<int> subarraySumClosest(vector<int> nums) {
        int n = nums.size();
        vector<int> pre(n + 1);
        for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + nums[i - 1];
        unordered_map<int, PII> hash;
        int res = INT_MAX;
        for (int i = 1; i <= n; i++) {
            for (int j = i; j <= n; j++) {
                if (abs(pre[j] - pre[i - 1]) < res) {
                    res = abs(pre[j] - pre[i - 1]);
                    if (!hash.count(res)) hash[res] = {i, j};
                }
            }
        }
        return {hash[res].first - 1, hash[res].second - 1};
    }

    /**
     * 前缀和+排序，则两个前缀和最近接的的话，其之间的子数组和越接近与0，所以对前缀和排序
     * 时间复杂度：O(nlogn)
     * 空间复杂度：O(n)
     */
    vector<int> subarraySumClosest2(vector<int> nums) {
        int n = nums.size();
        int t = 0;
        vector<PII> sum;
        sum.push_back({0, 0});
        for (int i = 0; i < n; i++) {
            t += nums[i];
            sum.push_back({t, i + 1}); // 坐标是从1开始的
        }
        sort(sum.begin(), sum.end()); // 排序
        int a = -1, b = -1, diff = INT_MAX;
        for (int i = 1; i < sum.size(); i++) {
            if (abs(sum[i].first - sum[i - 1].first) < diff) {
                diff = abs(sum[i].first - sum[i - 1].first);
                // 注意这儿 pre[j] - pre[i] 计算的是[i+1，j]区间的和
                a = min(sum[i].second, sum[i - 1].second); // 这儿应该是 a - 1 + 1
                b = max(sum[i].second, sum[i - 1].second) - 1; // 这儿需要减一
            }
        }
        return {a, b};
    }
};

数组分为差值最小的两部分II

将一个数组按照中间某一位置分成两部分，使得两部分子数组的和的差值的绝对值最小。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
   public:
    /**
     * 前缀和
     * 要使abs(前缀和 -（总和-前缀和)) = abs(2 * 前缀和 -总和)最小
     * 时间复杂度：O(n)
     */
    int absArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> pre(n + 1);
        for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + nums[i - 1];
        int res = INT_MAX;
        for (int i = 1; i <= n; i++) {
            res = min(res, abs(pre[i] * 2 - pre[n]));
        }
        return res;
    }
};

除自身以外数组的乘积(乘积数组)

给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。除自身以外数组的乘积

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
   public:
    /**
     * 时间复杂度：O(n)
     * 空间复杂度：O(1)
     */
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n, 1);
        int t = 1;
        // 前面部分的累积
        for (int i = 0; i < n; i++) {
            res[i] *= t;
            t *= nums[i];
        }
        t = 1;
        // 后面部分的累积
        for (int i = n - 1; i >= 0; i--) {
            res[i] *= t;
            t *= nums[i];
        }
        return res;
    }
};

和可被k整除的子数组(中等)

给定一个整数数组 A，返回其中元素之和可被 K 整除的（连续、非空）子数组的数目。和可被K整除的子数组

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

class Solution {
   public:
    /**
     * 前缀和
     * 时间复杂度：O(n^2)
     * 空间复杂度：O(n)
     */
    int subarraysDivByK(vector<int>& A, int K) {
        int n = A.size();
        vector<int> pre(n + 1);
        for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + A[i - 1];
        int res = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j <= n; j++) {
                if ((pre[j] - pre[i]) % K == 0) res++;
            }
        }
        return res;
    }

    /**
     * 前缀和 + 哈希 + 同余定理
     * 同余定理：如果整数a和整数满足a-b能够被m整除，即(a-b)%m==0,则a对m取余与b对m取余相等，即a%m==b%m。
     * 如果两个数的差能被K整除，就说明这两个数 mod K得到的结果相同，
     * 只要找有多少对 mod k 相同的数就可以组合一下得到结果。
     * 时间复杂度：O(n)
     * 空间复杂度：O(k)
     */
    int subarraysDivByK(vector<int>& A, int K) {
        int n = A.size();
        unordered_map<int, int> hash;
        hash[0] = 1; // 元素单独可以被k整除的情况
        int pre = 0;
        for (int i = 0; i < n; i++) {
            pre += A[i]; // 前缀和
            // 由于数组中有可能出现负数，我们需要将其加 K 从而使其 %K 之后的值为正数。
            pre = (pre % K + K) % K;
            hash[pre]++;
        }

        int res = 0;
        // 找有多少对 mod k 相同的数就可以组合一下得到结果。
        for (auto item : hash) {
            res += item.second * (item.second - 1) / 2;
        }
        return res;
    }
};

连续的子数组和(中等)

给定一个包含 非负数 的数组和一个目标 整数 k，编写一个函数来判断该数组是否含有连续的子数组，其大小至少为 2，且总和为 k 的倍数，即总和为 n*k，其中 n 也是一个整数。连续的子数组和

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

class Solution {
public:
    /**
     * 前缀和 + 哈希表 + 同余定理
     * 同余定理：如果整数a和整数满足a-b能够被m整除，即(a-b)%m==0,则a对m取余与b对m取余相等，即a%m==b%m。
     * 如果两个数的差能被K整除，就说明这两个数 mod K得到的结果相同，
     * 时间复杂度：O(n)
     * 空间复杂度：O(n)
     */
    bool checkSubarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        int pre = 0;
        unordered_map<int, int> hash;
        hash[0] = -1;
        for (int i = 0; i < n; i++) {
            pre += nums[i];
            if (!k) pre %= k;
            if (hash.count(pre)) {
                if (i - hash[pre] > 1)
                    return true;
            } else hash[pre] = i;
        }
        return false;
    }

    /**
     * 前缀和
     * 时间复杂度：O(n^2)
     * 空间复杂度：O(n)
     */
    bool checkSubarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> pre(n + 1);
        for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + nums[i - 1]; // 前缀和
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j <= n; j++) {
                int sum = pre[j] - pre[i];
                if (j - i > 1){
                    if (sum == k || (k && sum % k == 0)) return true;
                }
            }
        }
        return false;
    }
    // 暴力的话三层for循环，时间复杂度：O(n^3)
};

区域与检索(简单)

给定一个整数数组 nums，求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和，包含 i, j 两点。区域和检索 - 数组不可变

参考代码

1
2
3
4
5
6
7
8
9
10
11

vector<int> sum;
NumArray(vector<int>& nums) {
    sum = vector<int>(nums.size() + 1);
    for (int i = 1; i <= nums.size(); i++) {
        sum[i] = sum[i - 1] + nums[i - 1]; // 前缀和
    }
}

int sumRange(int i, int j) {
    return sum[j + 1] - sum[i];
}

矩阵区域和(中等)

给你一个 m * n 的矩阵 mat 和一个整数 K ，请你返回一个矩阵 answer ，其中每个 answer[i][j] 是所有满足下述条件的元素 mat[r][c]的和： i - K <= r <= i + K, j - K <= c <= j + K 。矩阵区域和

思路：二维前缀和，参考题解

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int K) {
    int m = mat.size(), n = mat[0].size();
    vector<vector<int>> sum(m + 1, vector<int>(n + 1)); // 计算前缀和
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            sum[i][j] = mat[i - 1][j - 1] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
        }
    }
    vector<vector<int>> res(m, vector<int>(n));
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            // 计算满足条件矩形的左上和右下坐标
            int x0 = max(i - K - 1, 0);
            int x1 = min(i + K, m);
            int y0 = max(j - K - 1, 0);
            int y1 = min(j + K, n);
            res[i - 1][j - 1] = sum[x1][y1] - sum[x0][y1] - sum[x1][y0] + sum[x0][y0];
        }
    }
    return res;
}
FEATURED TAGS
笔记 算法 Object Detection 算法模板 pytorch 笔经 动态规划 面经 面试题 C++ Vim
FRIENDS