LeetCode hot 100 每日一题(9)——560. 和为 K 的子数组

发布于:2025-03-15 ⋅ 阅读:(13) ⋅ 点赞:(0)

这是一道难度为中等的题目,让我们来看看题目描述:

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

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


示例 1:

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


示例 2:

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


提示:

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

题解

class Solution {
    // 定义方法 subarraySum,计算数组中所有连续子数组的和等于 k 的个数
    public int subarraySum(int[] nums, int k) {
        int count = 0; // 初始化计数器,记录符合条件的子数组个数
        // 外层循环:遍历数组的每一个元素,视作子数组的结束位置
        for (int start = 0; start < nums.length; start++) {
            int sum = 0; // 每次外层循环开始时重置累加和
            // 内层循环:从结束位置开始向前遍历,计算以该位置结尾的所有连续子数组的和
            for (int end = start; end >= 0; end--) {
                sum += nums[end]; // 累加当前子数组的元素到 sum
                if (sum == k) {  // 如果当前累加和等于 k,则找到一个符合条件的子数组
                    count++;     // 计数器加 1
                }
            }
        }
        return count; // 返回所有符合条件的子数组总数
    }
}

首先,定义了一个变量 count 用于计数,然后用外层循环遍历数组的每一个索引作为子数组的结束位置。对于每个结束位置 start,初始化一个 sum 为 0,并进入内层循环,从当前的 start 索引开始向前遍历(即从 end = start 开始,每次将 end 减 1),累加每个位置的数字到 sum 中;每次累加后,都检查当前的 sum 是否等于 k,如果相等则将 count 自增 1。这样,内层循环实际上计算了所有以 start 位置为结尾的连续子数组的和,外层循环确保了数组中所有可能的子数组都被枚举到,最终返回 count 作为结果。

总结

这道题在看题解的时候,我有点无法理解,直到看到题目中写了“子数组是数组中元素的连续非空序列”才恍然大悟内层的for循环作用。

我们来总结一下两个容易混淆的概念:

子串和子数组

  1. 数据结构不同:
  • 子数组:指的是数组中连续的一段元素。数组可以是数字、对象或其他类型的集合。
  • 子串:专指字符串中连续的一段字符序列。
  1. 应用场景不同:

    • 子数组:常用于解决数组问题,比如求连续子数组的和、寻找最大连续子数组等。
    • 子串:常用于字符串处理问题,比如判断字符串中是否包含某个模式、最长回文子串等。
  2. 概念相似性:

    • 两者都是连续的子集,关键在于它们所在的数据结构不同,因此处理方法和使用场景也有所区别。

子数组是数组中的连续片段,而子串是字符串中的连续片段。