前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Leetcode 560. 和为 K 的子数组

Leetcode 560. 和为 K 的子数组

作者头像
ccf19881030
发布2023-02-26 16:31:41
6670
发布2023-02-26 16:31:41
举报
文章被收录于专栏:ccf19881030的博客ccf19881030的博客

力扣 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 -1e7 <= k <= 1e7

方法1:暴力解法:

思路和算法

考虑以 i 结尾和为 k 的连续子数组个数,我们需要统计符合条件的下标 jj 的个数,其中0≤j≤i 且 [j…i] 这个子数组的和恰好为 k 。 我们可以枚举[0..i]里所有的下标 j 来判断是否符合条件,可能有读者会认为假定我们确定了子数组的开头和结尾,还需要 O(n 的时间复杂度遍历子数组来求和,那样复杂度就将达到 O(n^3),从而无法通过所有测试用例。但是如果我们知道 [j,i]子数组的和,就能 O(1) 推出[j−1,i] 的和,因此这部分的遍历求和是不需要的,我们在枚举下标 j 的时候已经能 O(1)求出 [j,i]的子数组之和。

代码语言:javascript
复制
class Solution {
public:
    // 暴力求解:时间复杂度为O(n*n)
     int subarraySum(vector<int>& nums, int k) {
         int count = 0;
         for (int i = 0; i < nums.size(); i++) {
             int sum = 0;
             for (int j = i; j >= 0; j--) {
                 sum += nums[j];
                 if (sum == k) {
                     count++;
                 }
             }
         }
         return count;
     }
};

复杂度分析

时间复杂度:O(n^2) ,其中 n 为数组的长度。枚举子数组开头和结尾需要 O(n^2)的时间,其中求和需要 O(1) 的时间复杂度,因此总时间复杂度为 O(n^2)

空间复杂度:O(1)。只需要常数空间存放若干变量。

注意:使用此方法的时间复杂度为O(n^2),有些用例无法通过,提交时不通过。

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

思路和算法

我们可以基于方法一利用数据结构进行进一步的优化,我们知道方法一的瓶颈在于对每个 ii,我们需要枚举所有的 jj 来判断是否符合条件,这一步是否可以优化呢?答案是可以的。

我们定义pre[i] 为 [0…i] 里所有数的和,则pre[i] 可以由pre[i−1] 递推而来,即: pre[i]=pre[i−1]+nums[i]

那么「[j…i]这个子数组和为 k,这个条件我们可以转化为

pre[i]−pre[j−1]==k

简单移项可得符合条件的下标 jj 需要满足 pre[j−1]==pre[i]−k

所以我们考虑以 i结尾的和为 k 的连续子数组个数时只要统计有多少个前缀和为pre[i]−k 的 pre[j] 即可。我们建立哈希表 mp,以和为键,出现次数为对应的值,记录pre[i] 出现的次数,从左往右边更新 mp 边计算答案,那么以 ii 结尾的答案 mp[pre[i]−k] 即可在 O(1)时间内得到。最后的答案即为所有下标结尾的和为 k 的子数组个数之和。

需要注意的是,从左往右边更新边计算的时候已经保证了mp[pre[i]−k] 里记录的 pre[j] 的下标范围是 0≤ j≤ i 。同时,由于pre[i] 的计算只与前一项的答案有关,因此我们可以不用建立 pre 数组,直接用 pre 变量来记录pre[i−1] 的答案即可。

代码语言:javascript
复制
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> mp;
        mp[0] = 1;
        int count = 0, pre = 0;
        for (auto& x:nums) {
            pre += x;
            if (mp.find(pre - k) != mp.end()) {
                count += mp[pre - k];
            }
            mp[pre]++;
        }
        return count;
    }
};

复杂度分析

  • 时间复杂度:O(n),其中 n 为数组的长度。我们遍历数组的时间复杂度为 O(n),中间利用哈希表查询删除的复杂度均为 O(1),因此总时间复杂度为 O(n)。
  • 空间复杂度:O(n),其中 n 为数组的长度。哈希表在最坏情况下可能有 n 个不同的键值,因此需要 O(n) 的空间复杂度。
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2023-02-02,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 力扣 560. 和为 K 的子数组
  • 方法1:暴力解法:
    • 复杂度分析
    • 方法二:前缀和 + 哈希表优化
      • 思路和算法
        • 复杂度分析
        领券
        问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档