一、题目描述

给你一个整数数组 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

二、思路讲解

1、暴力

算出每一个连续子数组的和即可，超时。

public 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<nums.length; j++) {
                sum += nums[j];
                if (sum == k) {
                    count++;
                }
            }
        }
        return count;
    }
}

时间复杂度： O(N^2)

空间复杂度： O(N)

2、保存前n个的和

暴力方法超时的原因是我们重复算了很多遍和，是否可以将这些和提前保存下来呢？

于是想到，我们使用数组sum[]，sum[i]表示数组中前i个数字的和（注意是前i个，而不是索引i之前），我们想要计算某一段子数组的和，比如索引i到j的和，只需计算sum[j+1] – sum[i]即可。

class Solution {
    public int subarraySum(int[] nums, int k) {
        int len = nums.length;
        // int sum = 0;
        int count = 0;
        int []sum = new int[len+1];
        sum[1] = nums[0];
        for(int i=2; i<len+1; i++) {
            sum[i] = sum[i-1] + nums[i-1];
        }
        int left = 0;
        int right = 0;
        for(int i=0; i<len+1; i++) {
            for(int j=i+1; j<len+1; j++) {
                if((sum[j]-sum[i])==k) {
                    count++;
                }
            }
        }
        return count;
    }
}

时间复杂度： O(N^2)

空间复杂度： O(N)

3、哈希表优化

其实，当我们构建好sum数组后，问题转化为了：在sum数组中有几对差为k的数字？不难想到力扣中的第一道题：1. 两数之和-力扣中使用哈希表优化时间的方式：我们将sum[i]的出现次数保存在哈希表中，然后去寻找sum[i] – k有几个，即可以O(1)的时间复杂度找到。

class Solution {
    public int subarraySum(int[] nums, int k) {
        int len = nums.length;
        int count = 0;
        int []sum = new int[len+1];
        sum[1] = nums[0];
        for(int i=2; i<len+1; i++) {
            sum[i] = sum[i-1] + nums[i-1];
        }
        Map<Integer, Integer> map = new HashMap<>();
        for(int i=0; i<len+1; i++) {
            if(map.containsKey(sum[i]-k)) {
                count += map.get(sum[i]-k);
            }
            map.put(sum[i], map.getOrDefault(sum[i], 0)+1);
        }
        return count;
    }
}

时间复杂度： O(N)

空间复杂度： O(N)

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/124959.html