和为 K 的子数组——前缀和+哈希

这篇具有很好参考价值的文章主要介绍了和为 K 的子数组——前缀和+哈希。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

和为 K 的子数组——前缀和+哈希,leetcode做题心得,哈希算法,算法

题目链接:力扣

注意:此题不能使用滑动窗口,因为数组中可能会出现负数。也就是说右指针向后移1位不能保证区间会增大,左指针向后移1位也不能保证区间和会减小。给定左右指针的位置没有二段性

已知sum[i]是从nums[0~i]的和,sum[i-1]是nums[0~i-1]的和

则有 sum[i] - sum[i-1] = nums[i]

则存在一个j(0<=j<=i) 使得sum[i]-sum[j] = k;

即sum[j] = sum[i]-k;    这个sum[j]的个数就是数组中和为k的连续子数的个数

在本题解中,在循环中完成sum[i]的计算即sum

这里用map来记录sum-k的个数文章来源地址https://www.toymoban.com/news/detail-579717.html

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
       
        map<int,int> mymap;  //key:值 value:出现的次数

        mymap[0]=1;

        int sum =0, ret =0;

        for(int i=0;i<nums.size();i++)
        {
            //使用map记录出现同样的和的次数, 对每个i计算累计和sum并判断map内是否有sum-k
            sum+=nums[i];

            if(mymap.find(sum-k)!=mymap.end())
              ret += mymap[sum-k];
            mymap[sum]++;
        }
        return ret;
    }
};

到了这里,关于和为 K 的子数组——前缀和+哈希的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【LeetCode热题100】【子串】和为 K 的子数组

    题目 给你一个整数数组  nums  和一个整数  k  ,请你统计并返回  该数组中和为  k   的子数组的个数  。 子数组是数组中元素的连续非空序列。 示例 1: 示例 2: 提示: 1 = nums.length = 2 * 104 -1000 = nums[i] = 1000 -107 = k = 107 暴力  直接两层循环找出所有连续子数组的和,这个

    2024年01月19日
    浏览(43)
  • leetcode分类刷题:易混题辨析一、209. 长度最小的子数组 vs 560. 和为K的子数组

    1、刷题慢慢积累起来以后,遇到相似的题目时,会出现算法思路混淆了 2、这两道题都是对 连续子数组加和 进行考察,细节区别在于数组元素在209. 长度最小的子数组为 正整数(窗口增加元素递增,减少元素递减) ,在560. 和为K的子数组为 整数 3、209. 长度最小的子数组采

    2024年02月10日
    浏览(39)
  • Leetcode-每日一题【剑指 Offer II 010. 和为 k 的子数组】

    给定一个整数数组和一个整数 k ,请找到该数组中和为 k 的连续子数组的个数。 示例 1: 输入: nums = [1,1,1], k = 2 输出: 2 解释: 此题 [1,1] 与 [1,1] 为两种不同的情况 示例 2: 输入: nums = [1,2,3], k = 3 输出: 2 提示: 1 = nums.length = 2 * 104 1000 = nums[i] = 1000 107 = k = 107 前置知识 前缀和

    2024年02月15日
    浏览(46)
  • leetcode分类刷题:哈希表(Hash Table)(四、前缀和 处理连续子数组)

    1、leetcode题目里对于 元素加和 的考察可谓是屡见不鲜,包括 简单的限定一个有效答案 的两个或多个元素求和leetcode分类刷题:哈希表(Hash Table)(一、简单的两数之和)、在有序数组内对加和等于target的 三元组、四元组 等的求解leetcode分类刷题:基于数组的双指针(三、

    2024年02月10日
    浏览(35)
  • hot100:10和为k的子数组

    题目链接: LeetCode 热题 100 - 学习计划 - 力扣(LeetCode)全球极客挚爱的技术成长平台 算法思想: 法一(暴力法): 使用两层for循环列举出所有的子数组,使用一个变量sum求得子数组的和并判断是否为k 法二(前缀和+哈希表): 前缀和:前缀和就是从下标为0的元素开始到当

    2024年01月23日
    浏览(43)
  • 剑指 Offer II 010. 和为 k 的子数组

    给定一个整数数组和一个整数 k ,请找到该数组中和为 k 的连续子数组的个数。 示例 1: 示例 2: 提示: 这个题目做出来不难,直接暴力枚举。但是利用哈希表和前缀和优化的过程我一直不是很理解,所以写下这篇文章来一点一点的研究,希望能对大家有所帮助 首先,先看最

    2023年04月16日
    浏览(39)
  • 【前缀和】LeetCode 560. 和为k的字数组

    力扣560题,链接:https://leetcode.cn/problems/subarray-sum-equals-k 暴力法,三重for循环,时间复杂度 O ( N 3 ) O(N^3) O ( N 3 ) ,会超时。 思路:两个for循环遍历起始位置和终止位置,第三个for遍历求解这段区间的和是否为k。 代码略。 在暴力法中我们发现会在很多重复计算,比如求前1

    2024年02月16日
    浏览(39)
  • leetcode做题笔记115. 不同的子序列

    给你两个字符串  s   和  t  ,统计并返回在  s  的  子序列  中  t  出现的个数。 题目数据保证答案符合 32 位带符号整数范围。 本题要计算t在s子序列的个数,可想到使用动态规划的方法,根据两个字符串的顺序不断向后匹配,当匹配的相同位置字符不相同时调用前面匹

    2024年02月10日
    浏览(35)
  • 【算法|滑动窗口No.1】leetcode209. 长度最小的子数组

    个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年02月08日
    浏览(41)
  • LeetCode算法心得——k-avoiding 数组的最小总和(标记数组)

    大家好,我是晴天学长,这是一个细节题和一部分的思维题哈! 2) .算法思路 k-avoiding 数组的最小总和 1,填充一个1到n 的Boolean的数组 要n个数,但是数组大小不能确定。 所以建立1000的大小。 2.遍历筛选,如果数组中有这个的话,标记为false。 3.监测是否是false,true就sum++(前

    2024年02月11日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包