echo

任生命穿梭 时间的角落

0%

和为K的子数组

Posted on In Valine:

560. 和为K的子数组

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。

示例 1 :

1
2
输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。

说明 :

  1. 数组的长度为 [1, 20,000]。
  2. 数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。

方法一：暴力

考虑以 i 结尾和为 k 的连续子数组个数，我们需要统计符合条件的下标 j 的个数，其中 0 <= j <= i，且[j...i]这个子数组的和恰好为 k。我们可以枚举 j 的值，然后再使用 O(n)的时间复杂度来求和，那样就达到O(n^3) 时间复杂度。如果我们知道[j, i]子数组的和，就能在O(1)时间求出[j - 1, i]子数组的和，因此我们初始时令 j = i，在循环中使 j 变小，同时维护一个数组和 sum。我们就能在O(1)时间内得到子数组[j...i]的和。

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

时间复杂度O(n^2)，空间复杂度O(1)。

方法二：前缀和+哈希表优化

我们定义 pre[i] 为 [0 … i] 内所有数的和，则有：
$$
pre[i] = pre[i - 1] + nums[i]
$$
那么 [j … i]子数组为 k ，这个条件可以转化为：
$$
pre[i] - pre[j - 1] == k
$$
简单移项得到：
$$
pre[j - 1] == pre[i] - k
$$
我们考虑 以 i 结尾的和为 k 的连续子数组时，只要统计有多少个前缀和为 pre[i] - k 的 pre[j] 即可。我们建立哈希表 map，使用和为键，出现的次数为相应的值，记录pre[i] 出现的次数，从左至右边更新 map，同时维护一个前缀和变量 pre，这样在计算 pre[i]时直接使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0, pre = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        //初始值，和为 0 的子数组个数为 1
        map.put(0, 1);
        for(int i = 0; i < nums.length; ++i){
            //计算 pre[i]
            pre += nums[i];
            //找到和为 pre[i] - k 子数组个数 
            if(map.containsKey(pre - k)){
                count += map.get(pre - k);
            }
            //更新 pre[i] 和的个数
            map.put(pre, map.getOrDefault(pre, 0) + 1);
        }
        return count;
    }
}

时间复杂度O(n)，空间复杂度O(n)。