560. 和为 K 的子数组

本题来自 LeetCode：560. 和为 K 的子数组^[1]

题目描述

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

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

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

1. 暴力法（超出空间限制）

分析

使用一个数组 dp[i][j]存储 nums[i...j]的和，当 dp[i][j] == k时，表示存在一个 i...j的子数组和为 k。但是该解法，超出了空间限制，这里引出该解法，继续优化。

解答

class Solution {
    public int subarraySum(int[] nums, int k) {
        int n = nums.length;
        int[][] dp = new int[n + 1][n + 1];
        int count = 0;
        for(int i = 0; i  n; i ++) {
            for(int j = i; j  n; j++) {
                dp[i + 1][j + 1] = dp[i][j] + nums[j];
                if(dp[i + 1][j + 1] == k) {
                    count ++;
                }
            }
        }
        return count;
    }
}

复杂度分析
时间复杂度： O(n^2)；
空间复杂度： O(n^2)；

2. 累计和（额外空间）

分析

观察 暴力法的实现，可以发现内层循环 for(int j = i; j n; j++)，每次只会用到 dp[i + 1]这一行，因此可以使用一维数组进行复用。

解答

class Solution {
    public int subarraySum(int[] nums, int k) {
        int n = nums.length;
        int[] dp = new int[n + 1];
        int count = 0;

        for(int i = 0; i  n; i ++) {
            // 注意将dp[i]归零
            dp[i] = 0;
            for(int j = i; j  n; j++) {
                dp[j + 1] = dp[j] + nums[j];
                if(dp[j + 1] == k) {
                    count ++;
                }
            }
        }
        return count;
    }
}

复杂度分析
时间复杂度： O(n^2)；
空间复杂度： O(n)；

3. 累计和（无额外空间）

分析

观察上一种解法的实现，可以发现内层循环的表达式 dp[j + 1] = dp[j] + nums[j]，每次只会用到上一个元素 dp[j]，因此可以使用一个变量单独存储即可。

解答

class Solution {
    public int subarraySum(int[] nums, int k) {
        int n = nums.length;
        int count = 0;

        for(int i = 0; i  n; i ++) {
            int sum = 0;
            for(int j = i; j  n; j++) {
                sum += nums[j];
                if(sum == k) {
                    count ++;
                }
            }
        }
        return count;
    }
}

复杂度分析
时间复杂度： O(n^2)；
空间复杂度： O(1)；

4. 哈希表

分析

通过以上解法发现，本题需要将子数组`nums[i...j]`所有的组合的和求出来，其中`0 = i = j n`，而要想枚举`[i,j]`的组合确实需要进行两层循环。

进一步观察到，子数组`nums[i...j]`的和，等于子数组`nums[0...j]`的和减去子数组`nums[0...i-1]`的和。那么只需要分别计算子数组`[0...i-1]`、`[0...j]`的和即可。而这些值可以通过一次循环计算出来。

定义`sum[j + 1]`为前`i`个元素的和，那么`sum[j + 1] - sum[i]`为子数组`nums[i...j]`的和。

对于`sum[j + 1]`的值，可以使用一个哈希表进行记录,只要`sum[j] - k`存在于哈希表中，就表示存在子数组`nums[i...j]的和=k`。

解答

class Solution {
    public int subarraySum(int[] nums, int k) {
        MapInteger, Integer table = new HashMap();
        table.put(0, 1);

        int n = nums.length;
        int count = 0;
        int sum = 0;

        for(int i = 0; i  n; i ++) {
            sum += nums[i];
            count += table.getOrDefault(sum - k, 0);
            table.put(sum, table.getOrDefault(sum, 0) + 1);
        }
        return count;
    }
}

复杂度分析
时间复杂度： O(n)；
空间复杂度： O(n)；

参考资料

560. 和为K的子数组: https://leetcode-cn.com/problems/subarray-sum-equals-k

原文始发于微信公众号（xiaogan的技术博客）：