和为k的子数组

给定一个整数数组和一个整数 k ，请找到该数组中和为 k 的连续子数组的个数，

1.静态滑动窗口1

遍历滑动窗口大小，每次for循环滑动窗口大小值固定，每次对滑动窗口中的内容进行求和，尝试更新答案，时间超时：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int ans = 0;
        for (int len = 1; len < nums.size(); ++len) {
            for (int i = 0, j = i + len; j <= nums.size(); ++i, ++j) {
                int sum = 0;
                for (int n = i; n < j; ++n) sum += nums[n];
                if (sum == k) ans++;
            }
        }
        return ans;
    }
};

所有用例成功输出结果，但由于时间复杂度太高，导致程序超时，

2.静态滑动窗口2

遍历滑动窗口大小，每次for循环滑动窗口大小值固定，

维护一个sum值 进行加入与减出，每次窗口移动加入与减出边界值，尝试更新答案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int ans = 0;
        for (int len = 1; len <= nums.size(); ++len) {
            int sum = 0;
            for (int i = 0; i < len; ++i) sum += nums[i];//窗口初始化
            if (sum == k) ans++;
            for (int i = 0, j = i + len; j < nums.size(); ++i, ++j) {//窗口开始移动
                sum -= nums[i];
                sum += nums[j];
                if (sum == k) ans++;
            }
        }
        return ans;
    }
};

程序依旧超时（如果使用java语言提交则可以通过），使用C++语言放弃滑动窗口法，

3.动态滑动窗口1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int ans = 0;
        int sum = 0;
        for (int i = 0, j = 0; j < nums.size(); ++j) {
            sum += nums[j];
            while (i < j && sum > k) {
                sum -= nums[i];
                i++;
            }
            if (sum == k) ans++;
        }
        return ans;
    }
};

出现问题：当数组中出现负数时导致的后果是，窗口增大的时候，和不一定增大，违背了滑窗的性质，不能使用滑动窗口处理。

4.暴力枚举

  1. 考虑以 j 结尾和为 k 的连续子数组个数
  2. 统计符合条件的下标 i 的个数，其中 0 ≤ i ≤ j 且 [i..j] 子数组的和恰好为 k （枚举[0..j]里所有的下标i）
  3. 优化：如果确定了子数组的开头和结尾，还需要 O(n) 的时间复杂度遍历子数组来求和，那样复杂度就将达到 $O(n^3)$
  4. 如果我们知道 [i,j] 子数组的和，就能 O(1) 推出 [i−1,j] 的和，因此这部分的遍历求和是不需要的，我们在枚举下标 i 的时候已经能 O(1) 求出 [i,j] 的子数组之和。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int ans = 0;
        for (int j = 0; j < nums.size(); ++j) {
            int sum = 0;
            for (int i = j; i >= 0; --i) {
                sum += nums[i];
                if (sum == k) ans++;
            }
        }
        return ans;
    }
};
  • 时间复杂度：$O(n^2)$
  • 空间复杂度：$O(1)$

5.前缀和+哈希

基于暴力枚举法，利用数据结构进行进一步优化（空间换时间），

暴力枚举法中的瓶颈在于对每个 j ，需要枚举所有的 i 来判断是否符合条件，这一步是否可以优化呢？答案是可以的。

优化思路：

  • 定义前缀和数组：pre[i]=pre[i−1]+nums[i]
  • 答案要求[i..j]子数组和是否为k ，可以转化为pre[j + 1]−pre[i]==k，移项可得下标i需要满足pre[i]==pre[j + 1]−k
  • 考虑以j结尾的和为k的连续子数组个数时，只要统计有多少个i在前缀和数组中满足pre[i]==pre[j + 1]−k即可。
  • 由此能够成功将枚举法中嵌套的for循环，简化成单个for循环 + 哈希map的赋值操作，时间复杂度由 $O(n^2)$ 降到 $O(n)$

image-20230429204101178

解题步骤：

  1. 初始化前缀和数组
  2. 初始化哈希表mp，unmap[0] = 1;
  3. 建立哈希表mp，以前缀和数组值pre[i]为 $key$ ，前缀和数组值pre[i]出现的次数为 $value$
  4. 从左往右一边计算答案，一边更新mp，那么以j结尾的答案 mp[pre[i]−k] 即可在O(1)时间内得到，
  5. 最后的答案即为所有下标结尾的和为 k 的子数组个数之和。

image-20230429204515901

问题本质：

统计以每一个 prefix[j] 为结尾，和为 k 的子数组数量即是答案。

其本质上是求解在[0,j]中，prefix数组中有多少个值为 prefix[j] − k 的数，这可以在遍历过程中使用哈希表进行解决。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int ans = 0;
        int len = nums.size();
        
        //1.前缀和数组初始化
        int *prefix = new int[len + 10]();
        for (int i = 1; i <= len; ++i) prefix[i] = prefix[i - 1] + nums[i - 1];

        //2.开始统计在 0 ~ j 中，prefix数组中有多少个值为 prefix[j] − k 的数
        unordered_map<int, int> unmap;
        unmap[0] = 1;
        for (int j = 1; j <= len; ++j) {
            ans += unmap[prefix[j] - k];
            unmap[prefix[j]]++;
        }
        return ans;
    }
};
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(n)$

写法优化：

需要注意的是，从左往右边更新边计算的时候已经保证了mp[pre[j]−k] 里记录的 pre[i] 的下标范围是0 ≤ j ≤ i

同时，由于pre[j] 的计算只与前一项的答案有关，因此我们可以不用建立 pre 数组，直接用 pre 变量来记录 pre[j−1] 的答案即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> unmap;
        unmap[0] = 1;
        int ans = 0, pre = 0;
        for (int i = 0; i < nums.size(); ++i) {
            pre += nums[i];
            ans += unmap[pre - k];
            unmap[pre]++;
        }
        return ans;
    }
};