560.和为K的子数组

LeetCode LeetCode 热题100 数组 哈希表 前缀和
发布时间 :
字数:3.3k 阅读 : 评论:
  1. 560.和为K的子数组
    1. 560.1 题目
    2. 560.2 题解
      1. 方法一：枚举法（暴力解法）
        1. 思路
        2. 复杂度分析
        3. 代码
      2. 方法二：前缀和 + 哈希表优化
        1. 思路
        2. 复杂度分析
        3. 代码
    3. 560.3 代码
    4. 560.4 运行结果

560.和为K的子数组

560.1 题目

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

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

示例 1：

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

示例 2：

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

提示：

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

560.2 题解

方法一：枚举法（暴力解法）

思路

双层循环，枚举所有可能的子数组 [start, end]。对固定的 start，从 end = start 开始累加，动态维护子数组和。每次更新和之后，如果等于 k，答案加一。

核心思想：枚举所有子数组，计算和是否等于 k。

具体步骤：

  1. 外层循环枚举起始位置 start。
  2. 内层循环从 start 开始累加元素。
  3. 每次累加后检查和是否等于 k。

举例：对于 nums = [1,1,1], k = 2：

  • start=0：sum=1，sum=2 ✓，sum=3
  • start=1：sum=1，sum=2 ✓
  • start=2：sum=1
  • 结果：2

复杂度分析

  • 时间复杂度：O(n^2)。
  • 空间复杂度：O(1)。

代码

// 方法一：枚举法（暴力解法）
// 核心思路：枚举所有可能的子数组起始位置，计算每个子数组的和，统计和为k的个数
// 时间复杂度：O(n²)，其中n是数组长度。外层循环枚举起始位置，内层循环计算子数组和
// 空间复杂度：O(1)，只需要常数空间存放变量
// 优点：思路简单直接，容易理解和实现
// 缺点：时间复杂度高，不适合大数据量
static int SubarraySum1(int[] nums, int k)
{
    int count = 0; // 统计和为k的子数组个数
    int numsLength = nums.Length; // 数组长度

    // 外层循环：枚举所有可能的子数组起始位置（start从0到n-1）
    for (int start = 0; start < numsLength; start++)
    {
        int sum = 0; // 记录从start到当前end位置的子数组和

        // 内层循环：枚举从start开始到数组末尾的所有子数组
        // 注意：这里是从start开始向后累加，而不是从末尾向前
        for (int end = start; end < numsLength; end++)
        {
            // 累加当前元素到子数组和中
            sum += nums[end];

            // 如果当前子数组和等于k，则计数加1
            if (sum == k)
            {
                count++;
            }
        }
    }

    return count; // 返回所有和为k的子数组个数
}

方法二：前缀和 + 哈希表优化

思路

维护前缀和 prefixSum[i] = nums[0] + ... + nums[i]。

子数组 [j+1, i] 的和为：prefixSum[i] - prefixSum[j]。

想要这段子数组和为 k，要满足：prefixSum[j] = prefixSum[i] - k。

遍历数组时，一边维护当前前缀和，一边用哈希表统计所有出现过的前缀和次数：

  • 每到一个新位置 i，先看之前有没有出现过 prefixSum - k，有的话说明存在若干个 j 使得 [j+1, i] 的和为 k
  • 再把当前的 prefixSum 记录进哈希表

关键细节：初始化时让前缀和 0 出现过一次，处理从下标 0 开始的子数组。

举个例子：nums = [1,1,1], k = 2

  • prefixSum=0，map={0:1}
  • i=0：prefixSum=1，找1-2=-1没有，map={0:1, 1:1}
  • i=1：prefixSum=2，找2-2=0有1个，count=1，map={0:1, 1:1, 2:1}
  • i=2：prefixSum=3，找3-2=1有1个，count=2
  • 结果：2

复杂度分析

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

代码

// 方法二：前缀和+哈希表优化法
// 
// 核心思路（通俗理解）：
// 想象你在一条路上走，边走边记录"累计走了多远"（前缀和）
// 当你发现"当前累计距离 - 目标距离k"在记录本里出现过
// 说明从那个记录点到当前位置的距离正好是k！
// 
// 数学原理（通俗比喻）：
// 想象你在一条路上走，路上有里程碑：
// prefixSum[i] = 从起点走到第i个里程碑的总距离
// prefixSum[j] = 从起点走到第j个里程碑的总距离
// 
// 那么：从第j+1个里程碑到第i个里程碑的距离 = prefixSum[i] - prefixSum[j]
// 
// 如果这个距离正好等于k：
// prefixSum[i] - prefixSum[j] = k
// 移项得：prefixSum[j] = prefixSum[i] - k
// 
// 所以：当我们走到第i个里程碑时，只需要检查之前是否有人走到过"prefixSum[i] - k"这个距离
// 如果有，说明从那个里程碑到当前位置的距离正好是k！
// 
// 时间复杂度：O(n)，只需要一次遍历数组
// 空间复杂度：O(n)，需要哈希表存储前缀和出现次数
// 优点：时间复杂度最优，适合大数据量
// 缺点：需要理解前缀和概念，实现相对复杂
static int SubarraySum2(int[] nums, int k)
{
    int count = 0; // 统计和为k的子数组个数
    int prefixSum = 0; // 记录当前前缀和（从0到当前位置的元素和）

    // 哈希表：Key=前缀和的值，Value=该前缀和出现的次数
    // 这个哈希表就像是我们的"累计和记录本"
    Dictionary<int, int> prefixSumCountDict = new Dictionary<int, int>();

    // 关键初始化：前缀和为0出现1次（表示空数组的情况）
    // 为什么需要这个初始化？
    // 当prefixSum == k时，说明从开头到当前位置的和就是k
    // 此时我们需要找到prefixSum[j] = 0（即空数组的情况）
    // 举例：nums = [1,1,1], k = 2，当走到第二个元素时：
    // prefixSum = 2，prefixSum - k = 0，正好找到初始化时记录的0
    prefixSumCountDict.Add(0, 1);

    // 开始遍历数组，一步一步走
    for (int i = 0; i < nums.Length; i++)
    {
        // 计算当前前缀和：prefixSum[i] = prefixSum[i-1] + nums[i]
        // 相当于在当前位置的"累计距离"
        prefixSum += nums[i];

        // 核心逻辑：查找是否存在前缀和为 (prefixSum - k) 的情况
        // 如果存在，说明存在子数组 [j+1, i] 的和为k
        // 因为：prefixSum[i] - prefixSum[j] = k  => prefixSum[j] = prefixSum[i] - k
        // 
        // 举例说明（nums = [1,1,1], k = 2）：
        // 当i=2时，prefixSum=3，我们需要找prefixSum-k=3-2=1
        // 哈希表中prefixSum=1出现过1次（在i=0时），说明存在子数组[1,2]的和为2
        if (prefixSumCountDict.ContainsKey(prefixSum - k))
        {
            // 累加所有满足条件的前缀和出现次数
            // 注意：这里可能不止出现一次，所以是累加而不是简单的+1
            count += prefixSumCountDict[prefixSum - k];

            // 调试信息：可以取消注释查看具体找到的子数组
            // Console.WriteLine($"找到子数组：从某个位置到{i}，和为{k}");
        }

        // 更新哈希表：将当前前缀和加入哈希表
        // 这一步很重要！我们要记录当前累计和，供后面的位置使用
        if (prefixSumCountDict.ContainsKey(prefixSum))
        {
            prefixSumCountDict[prefixSum]++; // 如果已存在，计数加1
        }
        else
        {
            prefixSumCountDict.Add(prefixSum, 1); // 如果不存在，添加新记录
        }

        // 调试信息：可以取消注释查看每一步的哈希表状态
        // Console.WriteLine($"位置{i}：prefixSum={prefixSum}, 哈希表={string.Join(",", prefixSumCountDict)}");
    }

    return count; // 返回所有和为k的子数组个数
}

560.3 代码

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        #region 题目

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

        #endregion

        #region 测试

        // 示例 1
        int[] nums1 = { 1, 1, 1 };
        int k1 = 2;
        int result11 = SubarraySum1(nums1, k1);
        int result12 = SubarraySum2(nums1, k1);
        Console.WriteLine($"示例1 方法1（枚举法）输出：{result11}");
        Console.WriteLine($"示例1 方法2（前缀和法）输出：{result12}");

        // 示例 2
        int[] nums2 = { 1, 2, 3 };
        int k2 = 3;
        int result21 = SubarraySum1(nums2, k2);
        int result22 = SubarraySum2(nums2, k2);
        Console.WriteLine($"示例2 方法1（枚举法）输出：{result21}");
        Console.WriteLine($"示例2 方法2（前缀和法）输出：{result22}");

        #endregion
    }


    #region 答案

    // 方法一：枚举法（暴力解法）
    // 核心思路：枚举所有可能的子数组起始位置，计算每个子数组的和，统计和为k的个数
    // 时间复杂度：O(n²)，其中n是数组长度。外层循环枚举起始位置，内层循环计算子数组和
    // 空间复杂度：O(1)，只需要常数空间存放变量
    // 优点：思路简单直接，容易理解和实现
    // 缺点：时间复杂度高，不适合大数据量
    static int SubarraySum1(int[] nums, int k)
    {
        int count = 0; // 统计和为k的子数组个数
        int numsLength = nums.Length; // 数组长度

        // 外层循环：枚举所有可能的子数组起始位置（start从0到n-1）
        for (int start = 0; start < numsLength; start++)
        {
            int sum = 0; // 记录从start到当前end位置的子数组和

            // 内层循环：枚举从start开始到数组末尾的所有子数组
            // 注意：这里是从start开始向后累加，而不是从末尾向前
            for (int end = start; end < numsLength; end++)
            {
                // 累加当前元素到子数组和中
                sum += nums[end];

                // 如果当前子数组和等于k，则计数加1
                if (sum == k)
                {
                    count++;
                }
            }
        }

        return count; // 返回所有和为k的子数组个数
    }

    // 方法二：前缀和+哈希表优化法
    // 
    // 核心思路（通俗理解）：
    // 想象你在一条路上走，边走边记录"累计走了多远"（前缀和）
    // 当你发现"当前累计距离 - 目标距离k"在记录本里出现过
    // 说明从那个记录点到当前位置的距离正好是k！
    // 
    // 数学原理（通俗比喻）：
    // 想象你在一条路上走，路上有里程碑：
    // prefixSum[i] = 从起点走到第i个里程碑的总距离
    // prefixSum[j] = 从起点走到第j个里程碑的总距离
    // 
    // 那么：从第j+1个里程碑到第i个里程碑的距离 = prefixSum[i] - prefixSum[j]
    // 
    // 如果这个距离正好等于k：
    // prefixSum[i] - prefixSum[j] = k
    // 移项得：prefixSum[j] = prefixSum[i] - k
    // 
    // 所以：当我们走到第i个里程碑时，只需要检查之前是否有人走到过"prefixSum[i] - k"这个距离
    // 如果有，说明从那个里程碑到当前位置的距离正好是k！
    // 
    // 时间复杂度：O(n)，只需要一次遍历数组
    // 空间复杂度：O(n)，需要哈希表存储前缀和出现次数
    // 优点：时间复杂度最优，适合大数据量
    // 缺点：需要理解前缀和概念，实现相对复杂
    static int SubarraySum2(int[] nums, int k)
    {
        int count = 0; // 统计和为k的子数组个数
        int prefixSum = 0; // 记录当前前缀和（从0到当前位置的元素和）

        // 哈希表：Key=前缀和的值，Value=该前缀和出现的次数
        // 这个哈希表就像是我们的"累计和记录本"
        Dictionary<int, int> prefixSumCountDict = new Dictionary<int, int>();

        // 关键初始化：前缀和为0出现1次（表示空数组的情况）
        // 为什么需要这个初始化？
        // 当prefixSum == k时，说明从开头到当前位置的和就是k
        // 此时我们需要找到prefixSum[j] = 0（即空数组的情况）
        // 举例：nums = [1,1,1], k = 2，当走到第二个元素时：
        // prefixSum = 2，prefixSum - k = 0，正好找到初始化时记录的0
        prefixSumCountDict.Add(0, 1);

        // 开始遍历数组，一步一步走
        for (int i = 0; i < nums.Length; i++)
        {
            // 计算当前前缀和：prefixSum[i] = prefixSum[i-1] + nums[i]
            // 相当于在当前位置的"累计距离"
            prefixSum += nums[i];

            // 核心逻辑：查找是否存在前缀和为 (prefixSum - k) 的情况
            // 如果存在，说明存在子数组 [j+1, i] 的和为k
            // 因为：prefixSum[i] - prefixSum[j] = k  => prefixSum[j] = prefixSum[i] - k
            // 
            // 举例说明（nums = [1,1,1], k = 2）：
            // 当i=2时，prefixSum=3，我们需要找prefixSum-k=3-2=1
            // 哈希表中prefixSum=1出现过1次（在i=0时），说明存在子数组[1,2]的和为2
            if (prefixSumCountDict.ContainsKey(prefixSum - k))
            {
                // 累加所有满足条件的前缀和出现次数
                // 注意：这里可能不止出现一次，所以是累加而不是简单的+1
                count += prefixSumCountDict[prefixSum - k];

                // 调试信息：可以取消注释查看具体找到的子数组
                // Console.WriteLine($"找到子数组：从某个位置到{i}，和为{k}");
            }

            // 更新哈希表：将当前前缀和加入哈希表
            // 这一步很重要！我们要记录当前累计和，供后面的位置使用
            if (prefixSumCountDict.ContainsKey(prefixSum))
            {
                prefixSumCountDict[prefixSum]++; // 如果已存在，计数加1
            }
            else
            {
                prefixSumCountDict.Add(prefixSum, 1); // 如果不存在，添加新记录
            }

            // 调试信息：可以取消注释查看每一步的哈希表状态
            // Console.WriteLine($"位置{i}：prefixSum={prefixSum}, 哈希表={string.Join(",", prefixSumCountDict)}");
        }

        return count; // 返回所有和为k的子数组个数
    }

    #endregion
}

560.4 运行结果

示例1 方法1（枚举法）输出：2
示例1 方法2（前缀和法）输出：2
示例2 方法1（枚举法）输出：2
示例2 方法2（前缀和法）输出：2
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com

赏

©2016-2026 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏