「力扣」第 560 题:和为 K 的子数组(中等)

liweiwei1419 ... 2022-1-6 前缀和
  • 前缀和
  • 哈希表
About 3 min

说明

分享一下,没有会员的朋友可以做类似 352 题的 560 题。

# 题目描述

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

示例 1:

输入:nums = [1,1,1], k = 2
输出:2
1
2

示例 2:

输入:nums = [1,2,3], k = 3
输出:2
1
2

提示:

  • 1 <= nums.length <= 2 * 10^4
  • -1000 <= nums[i] <= 1000
  • -10^7 <= k <= 10^7

# 方法一:暴力解法(超时)

  • 枚举左右边界(超时)。

Java 代码:

public class Solution {

    public int subarraySum(int[] nums, int k) {
        int len = nums.length;
        int count = 0;
        for (int left = 0; left < len; left++) {
            for (int right = left; right < len; right++) {

                int sum = 0;
                for (int i = left; i <= right; i++) {
                    sum += nums[i];
                }
                if (sum == k) {
                    count++;
                }
            }
        }
        return count;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

复杂度分析

  • 时间复杂度:,这里    是数组的长度;
  • 空间复杂度:

# 方法二:暴力解法的优化

固定了起点,即枚举左边界,时间复杂度降了一维。 Java 代码:

public class Solution {

    public int subarraySum(int[] nums, int k) {
        int count = 0;
        int len = nums.length;
        for (int left = 0; left < len; left++) {
            int sum = 0;
            // 区间里可能会有一些互相抵销的元素
            for (int right = left; right < len; right++) {
                sum += nums[right];
                if (sum == k) {
                    count++;
                }
            }
        }
        return count;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

复杂度分析

  • 时间复杂度:,这里   是数组的长度;
  • 空间复杂度:

# 方法三:前缀和

  • 构建前缀和数组,以便快速计算区间和;
  • 注意在计算区间和的时候,下标有偏移。

Java 代码:

public class Solution {

    public int subarraySum(int[] nums, int k) {
        int len = nums.length;
        // 计算前缀和数组
        int[] preSum = new int[len + 1];
        preSum[0] = 0;
        for (int i = 0; i < len; i++) {
            preSum[i + 1] = preSum[i] + nums[i];
        }

        int count = 0;
        for (int left = 0; left < len; left++) {
            for (int right = left; right < len; right++) {
                // 区间和 [left..right],注意下标偏移
                if (preSum[right + 1] - preSum[left] == k) {
                    count++;
                }
            }
        }
        return count;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

复杂度分析

  • 时间复杂度:,这里   是数组的长度;
  • 空间复杂度:

# 方法四:前缀和 + 哈希表优化

  • 使用哈希表加速运算;

这个思路不是很容易想到,需要多做一些类似的问题慢慢培养感觉。

Java 代码:

import java.util.HashMap;
import java.util.Map;

public class Solution {

    public int subarraySum(int[] nums, int k) {
        // key:前缀和,value:key 对应的前缀和的个数
        Map<Integer, Integer> preSumFreq = new HashMap<>();
        // 对于下标为 0 的元素,前缀和为 0
        preSumFreq.put(0, 1);

        int preSum = 0;
        int count = 0;
        for (int num : nums) {
            preSum += num;

            // 先获得前缀和为 preSum - k 的个数,加到计数变量里
            if (preSumFreq.containsKey(preSum - k)) {
                count += preSumFreq.get(preSum - k);
            }

            // 然后维护 preSumFreq 的定义
            preSumFreq.put(preSum, preSumFreq.getOrDefault(preSum, 0) + 1);
        }
        return count;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

复杂度分析

  • 时间复杂度:,这里   是数组的长度;
  • 空间复杂度:
Last update: January 14, 2022 00:19
Contributors: liweiwei1419