[LeetCode 笔记] 560. Subarray Sum Equals K

前言

　　这题学习目标是 Prefix Sums 前缀和的概念， Prefix Sums 通常用于需要频繁查询阵列中某一区间的元素和的情况，这里目标是找到一个阵列中连续子阵列的合回传最大值，时间複杂度估为 O(n^2)，这里有 JAVA 和 Python 的写法。

题目

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.
A subarray is a contiguous non-empty sequence of elements within an array.

给定一个整数阵列 nums 和一个整数 k，回传总合等于 k 值的连续子阵列的数量。
子阵列是阵列中连续的非空元素阵列。

题目连结：https://leetcode.com/problems/subarray-sum-equals-k/

题目限制

1 <= nums.length <= 2 * 104
1000 <= nums[i] <= 1000
107 <= k <= 107

範例

Input: nums = [1,1,1], k = 2Output: 2

[1, 1] ⇒ 2 ，符合 k 值的大小
[1, 1] ⇒ 2 ，符合 k 值的大小
所以 nums 阵列可以有两个子阵列，Output 回传 2

Input: nums = [1,2,3], k = 3Output: 2

[1, 2] ⇒ 3 ，符合 k 值的大小
[3] ⇒ 3 ，符合 k 值的大小
所以 nums 阵列可以有两个子阵列，Output 回传 2

思路&笔记

这题主要的思路是 Prefix Sums 为某一个区间和的算法

我们先把符合 nums 阵列其中一个连续子阵列，拿出来做说明回推假如有一连续子阵列 prefix_sum = [2, 2, 3]然后把这个子阵列的前缀和的终点 - 前缀和的起点，终点就是 3 ，起点就是 2这里概念上不是数学上的减去，而是空间上的减去如果获取的子阵列 prefix_sum 的前缀和相减等于 k 的话 count++

笔者用示意图可能会比较清晰

// for examplenums = [1, 1, 1, 1, 2, 2, 3, 5, 6, 7, 8]k = 7prefix_sum = [2, 2, 3] = 7prefix_sum_end = [1, 1, 1, 1, 2, 2, 3] = 11prefix_sum_start = [1, 1, 1, 1] = 4prefix_sum_end - sum_prefix_start => [1, 1, 1, 1, 2, 2, 3] - [1, 1, 1, 1] = 7prefix_sum = k 成立，count++

JAVA 实现

public class Solution {    public int subarraySum(int[] nums, int k) {        int count = 0;        int[] sum = new int[nums.length + 1]; // 设定前缀和的阵列        sum[0] = 0; // 设定阵列第一个索引为 0        // 把阵列中所有的元素加起来，组合成各个前缀和        for (int i = 1; i <= nums.length; i++)            sum[i] = sum[i - 1] + nums[i - 1]; // sum = [0, 1, 1+2, 1+2+3]              for (int start = 0; start < sum.length; start++) {            for (int end = start + 1; end < sum.length; end++) {                if (sum[end] - sum[start] == k) // 前缀和的终点 - 前缀和的起点                    count++;            }        }              return count;    }}

Python 实现

使用了和 Java 一样的逻辑执行，换成 Python 的写法，不过超过了时间限制

class Solution:    def subarraySum(self, nums: List[int], k: int) -> int:        count = 0        sum = [0] * (len(nums)+1) # 设定前缀和的阵列        sum[0] = 0 # 设定阵列第一个索引为 0        # 把阵列中所有的元素加起来，组合成各个前缀和        for i in range(len(nums)+1):            sum[i] = sum[i-1] + nums[i-1] # sum = [0, 1, 1+2, 1+2+3]        for start in range(len(sum)):            for end in range(start+1, len(sum)):                if sum[end] - sum[start] == k: # 前缀和的终点 - 前缀和的起点                    count+=1        return count

另一种写法加入 python 的字典来演算，作用是帮助我们统计前缀和出现的次数

class Solution:    def subarraySum(self, nums: List[int], k: int) -> int:        count = 0         prefix_sum = 0 # 当前的前缀和        # 字典 d 的 key 是前缀和，value 是该前缀和出现的次数        d = {0 : 1} # 初始将 0 的出现次数设为 1，表示前缀和为 0 的情况        for num in nums:            prefix_sum = prefix_sum + num # 更新当前的前缀和            # 因为已经设定为 0 ，说明存在一个前缀和相减为 0 ，代表和 k 一样            if prefix_sum - k in d:                count = count + d[prefix_sum - k] # count 次数：0 + 1            # 如果不存在，表示这是首次遇到这个前缀和，将该前缀和作为 key，将其出现次数设为 1。            if prefix_sum not in d:                d[prefix_sum] = 1            else:                d[prefix_sum] = d[prefix_sum] + 1 # 代表已经有其他前缀和等于当前的前缀和，把相同的前缀和 + 1        return count

成绩

Blog
https://chris81051.github.io/2023/10/09/LeetCode-560-Subarray-Sum-Equals-K-Java-Python/
有分享技术文章、科技新闻、日常生活，欢迎一起讨论