专栏首页用户6093955的专栏leetcode560题解【前缀和+哈希】

leetcode560题解【前缀和+哈希】

leetcode560.和为K的子数组

题目链接

算法

前缀和+哈希

时间复杂度O(n)

在解决这道题前需要先清楚,一个和为k的子数组即为一对前缀和的差值【这句话摘自链接

1.我们假设有这么一个子数组[i,j]满足数字和为k,那么就有pre[j] - pre[i-1] = k(注:pre数组为记录前缀和的数组),则pre[i-1] = pre[j] - k

2.题目问找到nums数组中和为k的连续的子数组的数目,一开始想到是否会重叠,后来仔细看题目后发现题目中并没有限定子数组是否重叠,那么这道题只需要记录pre[i-1]出现的次数即可;

3.不过为什么要累加pre[i-1]出现的次数呢?

原因是我们要算出满足以下标为j为结尾的数组的数字和为k的出现的次数,由pre[i-1] = pre[j] - k可知[i,j]这个子数组已经满足数字和为k,那么首先需要想到的是应该把这一次记录上,即+1,不过由于在遍历时我们每次都会把当前的前缀和用一个哈希表存储下来,并且累加1,这里我们每次都累加1,也就是说在下标i前面有可能存在一个下标k,满足[k,i]这个子数组的数字和为k,这样就不难理解为什么每次都需要累加pre[i-1]的次数了.(注意这个pre[i-1]的值是通过pre[j]-k来得到的)

4.如果还没理解为什么要累加pre[i-1]出现的次数,来张图感受一下。

观看上图,假设我们已经知道OAOBOC的长度均为s,那么我们可取距离C点为k的点D,可知AD=BD=CD=k,通过这个图就很好理解为什么要累加pre[j]-k出现的次数了。

5.这道题当初做的时候理解错题目了,原以为是求出连续的符合条件的子数组,并且子数组之间边界恰好重叠。其实这道题说的是这个子数组连续,也就是说这个子数组它不间断,否则没有理解到这点就很难做对了。

C++代码

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int len = nums.size();
        int sum = 0;        //记录当前位置的前缀和
        int res = 0;
        unordered_map<int,int> hs;
        hs[0] = 1;      //表示和为0出现1次
        for(int i = 0; i < len; i++){
            sum += nums[i];
            if(hs.find(sum - k) != hs.end()){
                res += hs[sum-k];
            }
            hs[sum]++;
        }
        return res;
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数据结构期末复习——还原二叉树(根据先序和中序遍历输出先序遍历)

    参考博客:https://blog.csdn.net/qq_37708702/article/details/79644068

    _DIY
  • 【(图) 旅游规划 (25 分)】【Dijkstra算法】

    _DIY
  • Problem G: STL——整理唱片(list的使用)

    这里用到了remove_if(op), 不得不说,这个很好用,意思是list中满足op这个条件的元素将会被全部移除

    _DIY
  • Codeforces Round #539 (Div. 2) C. Sasha and a Bit of Relax(前缀异或和)

    题目链接:https://codeforces.com/contest/1113/problem/C

    Ch_Zaqdt
  • 暑假(补) -7

    并查集,在一些有N个元素的集合应用问题中,我们通常是在开始时让每个元素构成一个单元素的集合,然后按一定顺序将属于同一组的元素所在的集合合并,其间要反复查找一个元...

    AngelNH
  • aptitude指令

    aptitude update #更新可用的包列表 aptitude upgrade #升级可用的包 aptitude dist-upgrad...

    JNingWei
  • 一天一大 lee(被围绕的区域)难度:中等-Day20200811

    被围绕的区间不会存在于边界上,换句话说,任何边界上的 'O' 都不会被填充为 'X'。任何不在边界上,或不与边界上的 'O' 相连的 'O' 最终...

    前端小书童
  • centos6.8下配置lamp

    一、系统环境 系统平台:CentOS 6.8 64位 Apache版本: httpd-2.4.25.tar.gz MySQL版本: mysql-5.7.1...

    botkenni
  • 【CPP】各种各样的树(6)——自底向上的伸展树

    昨(shang)天(zhou)结尾说到AVL树的弊端,然后提到了伸展树这个东西,那这次就来说说这个伸展树的第一种实现,自底向上的伸展树。

    ZifengHuang
  • 基于Doc2vec训练句子向量

    磐创AI

扫码关注云+社区

领取腾讯云代金券