力扣学习笔记——560. 和为 K 的子数组

题目介绍

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

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

解法一：暴力枚举

高端的算法往往采用最朴素的解题方法：

class Solution {
    public int subarraySum(int[] nums, int k) {
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            int sum = 0;
            for (int j = i; j >= 0; j--) {
                sum += nums[j];
                if (sum == k) res++;
            }
        }
        return res;
    }
}

复杂度分析

• 时间复杂度：O(n²)

• 空间复杂度：O(1)

解法二：前缀和

前缀和：nums[i]+...+nums[i+n]

解题思路

参考幻灯片，点击后可以使用键盘上下键↕控制

动图版：

实现代码

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;
    }
}

复杂度分析

实际上，单单使用前缀和，复杂度其实比枚举还高

• 时间复杂度：O(n²)

• 空间复杂度：O(n)

  • 由于哈希表需要不断存取，所以一共存n个元素

解法三：前缀和+哈希表优化

解题思路

幻灯片只能放一个，绝对不是我懒了：

实现代码

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

复杂度分析

• 时间复杂度：O(n)

• 空间复杂度：O(n)