560. 和为 K 的子数组

>>强大,10k+点赞的 SpringBoot 后台管理系统竟然出了详细教程!

本题来自 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. 哈希表

分析

  1. 通过以上解法发现,本题需要将子数组nums[i...j]所有的组合的和求出来,其中0 <= i <= j < n,而要想枚举[i,j]的组合确实需要进行两层循环。
  2. 进一步观察到,子数组nums[i...j]的和,等于子数组nums[0...j]的和减去子数组nums[0...i-1]的和。那么只需要分别计算子数组[0...i-1][0...j]的和即可。而这些值可以通过一次循环计算出来。
  3. 定义sum[j + 1]为前i个元素的和,那么sum[j + 1] - sum[i]为子数组nums[i...j]的和。
  4. 对于sum[j + 1]的值,可以使用一个哈希表进行记录,只要sum[j] - k存在于哈希表中,就表示存在子数组nums[i...j]的和=k

解答

class Solution {
public int subarraySum(int[] nums, int k) {
Map<Integer, 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)

参考资料

[1]

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


原文始发于微信公众号(xiaogan的技术博客):560. 和为 K 的子数组