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

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

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

题解

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. 数据结构不同：

• 子数组：指的是数组中连续的一段元素。数组可以是数字、对象或其他类型的集合。
• 子串：专指字符串中连续的一段字符序列。

2. 应用场景不同：

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

3. 概念相似性：

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

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