首页 > 其他分享 >Leetcode 560 和为k的子数组

Leetcode 560 和为k的子数组

时间:2024-02-25 21:22:52浏览次数:25  
标签:pre count 前缀 560 hmap ++ 数组 Leetcode

Problem: 560. 和为 K 的子数组
image

难点

  1. 怎么通过前缀和找到和为k的子数组

如官方题解所言,[j···i]的子数组=k可转化为pre[i]-pre[j-1]==k
要找到前缀和找到和为k的子数组个数就是“找到当前前缀和pre[i]-之前求得的前缀和=k”的总情况。我们通过哈希表记录每个前缀和(的值)出现的次数(比如下标0到2的和是1,那么mp[1]++,下标3到6的和是1,mp[1]++),就能在O(1)的时间求出“之前求出的前缀和”有多少种子数组。
在for循环中pre[i]可以有pre[i-1]得到——>简化为单个变量,k又是定值,每次都访问mp[pre-k]若存在则能说明[0···i]的子数组能满足“pre[i] - 之前求得的前缀和 = k”

  1. 为什么是count += hmap[pre-k];而不是count++

count++只表明存在某一个子数组满足,而没有考虑到之前可能已经存在多个位置的前缀和等于 pre - k,故需要累加

Code

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        //不能滑动窗口——k可负
        unordered_map<int,int> hmap;
        hmap[0] = 1;
        int count=0,pre=0;
        for(int& x:nums){
            pre += x;//求前缀和pre[i]
            //如果pre[i] - 之前求得的前缀和 = k
            if(hmap.find(pre - k)!=hmap.end()){
                //+=而不是++是因为之前可能有多种前缀和都满足
                count += hmap[pre-k];
            }
            hmap[pre]++;//哈希表记录前缀和pre[i]
        }
        return count;
    }
};

标签:pre,count,前缀,560,hmap,++,数组,Leetcode
From: https://www.cnblogs.com/neromegumi/p/18033079

相关文章

  • 提高组算法-树状数组
    树状数组是当序列动态变化时,依然可以高效率的查询和维护前缀和(或区间和)的数据结构。实现思路现在有\(16\)个数字:\(a[]={1,8,5,9,6,3,9,8,7,2,3,9,6,4,1,7}\)。我们要实现\(2\)个函数:修改其中某个元素的数值。求出前\(n\)个数字的和。但是,这\(2\)个函数要在极......
  • POJ--3468 A Simple Problem with Integers(线段树/树状数组)
    记录11:032024-2-25http://poj.org/problem?id=1961线段树树状数组把区间增加转变为单点增加,利用两个树状数组\(c_0和c_1\)将”Clrd"转化为在树状数组\(c_0\)中,把位置l上的数加d在树状数组\(c_0\)中,把位置r+1上的数减d在树状数组\(c_1\)中,把位置l上的数......
  • 代码随想录算法训练营第二天| 977.有序数组的平方
    第一题题解首先写了一个初步解,后续再想优化思路classSolution:defsortedSquares(self,nums:List[int])->List[int]:#sortbytheabsofvalueabs_min=10000abs_min_index=0foriinrange(len(nums)):if......
  • python list 动态数组
    list 对象是一种 容量自适应 的 线性容器 ,底层由 动态数组 实现。动态数组结构决定了 list 对象具有优秀的尾部操作性能,但头部操作性能却很差劲。容量调整当我们调用 append 、pop 、insert 等方法时,列表长度随之发生变化。当列表长度超过底层数组容量时,便需要......
  • 2024-02-24:用go语言,给你一个 n 个点的带权无向连通图,节点编号为 0 到 n-1, 同时还有一
    2024-02-24:用go语言,给你一个n个点的带权无向连通图,节点编号为0到n-1,同时还有一个数组edges,其中edges[i]=[fromi,toi,weighti],表示在fromi和toi节点之间有一条带权无向边,最小生成树(MST)是给定图中边的一个子集,它连接了所有节点且没有环,而且这些边的权值和最......
  • 后缀数组学习笔记 应用篇
    一些后缀数组的应用。利用\(sa\)和\(rk\)数组这类题目通常需要发掘一些性质,转化为求串的字典序最小/大后缀或长度固定的子串。P3809【模板】后缀排序后缀数组板子。P6095[JSOI2015]串分割二分答案串的排名。CF1923FShrink-Reverse转化为求长度为\(len\)的字典......
  • Leetcode 42.接雨水
    题目朴素解法:对于每列分别向左右扫描查找左右最高的柱子,对于每一个柱子接的水,那么它能接的水=min(左右两边最高柱子)-当前柱子高度。遍历每列时间复杂度为O(n),每列再扫描O(n),总共O(N^2)。classSolution{public:inttrap(vector<int>&height){//O(n^2)还是超......
  • C# 中的数组使用
    ·//数组///数组是一组相同类型的数据(ps:js中的数组可以不同类型)访问通过索引访问数组元素///数组的声明要使用new使用{}来初始化数组元素还需要指定数组的大小/////声明了一个没有元素的数组int[]iar......
  • 代码随想录算法训练营day03 | leetcode 203. 移除链表元素、707. 设计链表、206. 反转
    目录题目链接:203.移除链表元素-简单题目链接:707.设计链表-中等题目链接:206.反转链表-简单题目链接:203.移除链表元素-简单题目描述:给你一个链表的头节点head和一个整数val,请你删除链表中所有满足Node.val==val的节点,并返回新的头节点。示例1:输入:head=[1,2,6......
  • 【leetcode】数组篇刷题 --删除元素
    //@before-stub-for-debug-begin#include<vector>#include<string>#include"commoncppproblem27.h"usingnamespacestd;//@before-stub-for-debug-end/**@lcapp=leetcode.cnid=27lang=cpp**[27]移除元素*///@lccode=start......