题目介绍

和为K的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

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

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

提示：

  • 1 <= nums.length <= 2 * 104
  • -1000 <= nums[i] <= 1000
  • -107 <= k <= 107

分析

首先我在做题的时候忽视了“子数组”这个概念。

子数组

子数组是数组中元素的连续非空序列。

字符串的子串是字符串中元素的连续序列。可以为空串。

数组的子序列、字符串的子序列是可以不连续的。

求和

题目要求我们求和为k的子数组个数。
我们应该优先考虑使用遍历的方式来实现，由于子数组存在连续性，所以我们考虑设置两个指针，分别指向子数组的起始位置和结束位置。
尾指针从起始位置开始向后遍历，头指针从尾指针的位置向前遍历。
我们从尾指针所在位置开始计算子数组的和，当和等于k时，我们就找到了一个符合要求的子数组。
但是注意头指针的遍历必须从尾指针的位置开始，一致遍历到起始位置。
这是因为数组不是有序的，在遍历过程中我们可能遇到0，也可能遇到负数，造成在多个位置都能产生和为k的情况。

实现

代码

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;//每次内循环结束后sum值都清零
            for(int j = i ; j >= 0 ; j --){
                sum = sum + nums[j];
                if(sum == k){
                    count ++;
                }
            }
        }
        return count;
    }
}

时空复杂度分析

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

优化

考虑到对于每一个 i，我们都需要从 i 开始向起始位置遍历，这会导致重复计算。
我们可以考虑使用前缀和的方式来优化。
前缀和是指数组中前 i 个元素的和。
我们可以用一个数组来存储前缀和，然后在遍历过程中，用当前位置的前缀和减去之前的前缀和，就可以得到子数组的和。
如果这个和等于k，那么我们就找到了一个符合要求的子数组。
我们可以用一个哈希表来存储前缀和出现的次数，然后在遍历过程中，用当前位置的前缀和减去k，就可以得到之前出现过的前缀和。
如果之前出现过这个前缀和，那么我们就可以用当前位置的前缀和减去之前出现过的前缀和，就可以得到一个符合要求的子数组。
我们可以用一个变量来记录符合要求的子数组的个数。

优化代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer,Integer> countmap = new HashMap<>();
        countmap.put(0,1);
        int counter = 0;
        int temp = 0;
        for(int i = 0 ; i < nums.length ; i++){
            temp = temp + nums[i];
            if(countmap.containsKey(temp -k)){
                counter += countmap.get(temp -k);
            }
            countmap.put(temp,countmap.getOrDefault(temp,0)+1);//无论是否存在，都需要给哈希表中值为temp的key对应的值加上1。getOrDefault方法：存在temp返回temp，不存在返回指定值0
        }
        return counter;
    }
}

时空复杂度分析

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

License

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

快来参与讨论吧~