和为 K 的子数组

• 题目描述
• 解题思路
• • 代码(枚举)
  • 复杂度
  • 代码(前缀和+哈希表优化)
  • 复杂度

力扣链接

题目描述

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

解题思路

官方题解链接

• 枚举
• 前缀和+哈希表优化

代码(枚举)

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）

代码(前缀和+哈希表优化)

//前缀和+hash表优化
    public int subarraySum(int[] nums, int k) {
        //满足条件的个数
        int count = 0;
        //前缀和
        int pre = 0;
        HashMap< Integer, Integer > map = new HashMap <>();
        //应对有连续的多个值刚好和为k的情况
        map.put(0, 1);
        for (int i = 0; i < nums.length; i++) {
            pre += nums[i];
            //如果有前缀和为pre-k的,说明就有map.get(pre-k)个满足条件的连续子数组的和为k
            if (map.containsKey(pre - k)) {
                count += map.get(pre - k);
            }
            //添加前缀和pre -> 前缀和为pre个数的映射
            map.put(pre, map.getOrDefault(pre, 0) + 1);
        }
        return count;
    }

复杂度