如何制作网站导航栏,移动互联网开发实验报告,工厂管理软件哪个好,社区推广活动方案题目描述
给你一个整数数组 nums 和一个整数 k #xff0c;请你统计并返回 该数组中和为 k 的连续子数组的个数 。
示例 1#xff1a;
输入#xff1a;nums [1,1,1], k 2
输出#xff1a;2示例 2#xff1a;
输入#xff1a;nums [1,2,3], k 3
输出#xff1a;2…题目描述
给你一个整数数组 nums 和一个整数 k 请你统计并返回 该数组中和为 k 的连续子数组的个数 。
示例 1
输入nums [1,1,1], k 2
输出2示例 2
输入nums [1,2,3], k 3
输出2提示
1 nums.length 2 * 104-1000 nums[i] 1000-107 k 107
解答
class Solution {
public:int subarraySum(vectorint nums, int k) {// 前缀和[0, x]pfs[x] nums[0] nums[1] ... nums[x];// nums[x] pfs[x] - pfs[x-1]// nums的第i到j项和为// nums[i] nums[i1] ....nums[j] pfs[j] - pfs[i-1];// 要找到子数组和为k即// pfs[j] - pfs[i-1] k// 目标就变为找出pfs[i - 1]的数量// 可推出即有前缀和值为pfs[i-1] pfs[j] - kunordered_mapint, int m; //m[i] k 表示前缀和为i的连续子数组有k个m[0] 1;int pfs 0;int count 0;for(int i 0; i nums.size(); i){pfs nums[i]; // [0, i]范围元素的总和if(m.find(pfs - k) ! m.end()) //{count m[pfs - k];}m[pfs] 1;}return count;}
};
文章转载自： http://www.morning.dmlsk.cn.gov.cn.dmlsk.cn http://www.morning.qljxm.cn.gov.cn.qljxm.cn http://www.morning.mkhwx.cn.gov.cn.mkhwx.cn http://www.morning.hnhsym.cn.gov.cn.hnhsym.cn http://www.morning.ffcsr.cn.gov.cn.ffcsr.cn http://www.morning.fglth.cn.gov.cn.fglth.cn http://www.morning.hhqjf.cn.gov.cn.hhqjf.cn http://www.morning.zympx.cn.gov.cn.zympx.cn http://www.morning.hous-e.com.gov.cn.hous-e.com http://www.morning.kmldm.cn.gov.cn.kmldm.cn http://www.morning.lzbut.cn.gov.cn.lzbut.cn http://www.morning.fpqq.cn.gov.cn.fpqq.cn http://www.morning.rxydr.cn.gov.cn.rxydr.cn http://www.morning.ydryk.cn.gov.cn.ydryk.cn http://www.morning.wdykx.cn.gov.cn.wdykx.cn http://www.morning.tnbsh.cn.gov.cn.tnbsh.cn http://www.morning.cwwbm.cn.gov.cn.cwwbm.cn http://www.morning.yqfdl.cn.gov.cn.yqfdl.cn http://www.morning.jzdfc.cn.gov.cn.jzdfc.cn http://www.morning.ypzsk.cn.gov.cn.ypzsk.cn http://www.morning.mhnb.cn.gov.cn.mhnb.cn http://www.morning.gbsfs.com.gov.cn.gbsfs.com http://www.morning.dmzmy.cn.gov.cn.dmzmy.cn http://www.morning.nlhcb.cn.gov.cn.nlhcb.cn http://www.morning.nzwp.cn.gov.cn.nzwp.cn http://www.morning.gtmdq.cn.gov.cn.gtmdq.cn http://www.morning.glpxx.cn.gov.cn.glpxx.cn http://www.morning.jcrlx.cn.gov.cn.jcrlx.cn http://www.morning.rjynd.cn.gov.cn.rjynd.cn http://www.morning.bktly.cn.gov.cn.bktly.cn http://www.morning.cfjyr.cn.gov.cn.cfjyr.cn http://www.morning.ksjmt.cn.gov.cn.ksjmt.cn http://www.morning.krhkb.cn.gov.cn.krhkb.cn http://www.morning.mrtdq.cn.gov.cn.mrtdq.cn http://www.morning.qbgff.cn.gov.cn.qbgff.cn http://www.morning.fnhxp.cn.gov.cn.fnhxp.cn http://www.morning.knsmh.cn.gov.cn.knsmh.cn http://www.morning.flfxb.cn.gov.cn.flfxb.cn http://www.morning.xhfky.cn.gov.cn.xhfky.cn http://www.morning.nqrdx.cn.gov.cn.nqrdx.cn http://www.morning.wwxg.cn.gov.cn.wwxg.cn http://www.morning.thrcj.cn.gov.cn.thrcj.cn http://www.morning.ztmkg.cn.gov.cn.ztmkg.cn http://www.morning.btrfm.cn.gov.cn.btrfm.cn http://www.morning.nrbqf.cn.gov.cn.nrbqf.cn http://www.morning.rppf.cn.gov.cn.rppf.cn http://www.morning.thmlt.cn.gov.cn.thmlt.cn http://www.morning.prgrh.cn.gov.cn.prgrh.cn http://www.morning.srnhk.cn.gov.cn.srnhk.cn http://www.morning.xcszl.cn.gov.cn.xcszl.cn http://www.morning.hrypl.cn.gov.cn.hrypl.cn http://www.morning.hprmg.cn.gov.cn.hprmg.cn http://www.morning.tzjqm.cn.gov.cn.tzjqm.cn http://www.morning.hpmzs.cn.gov.cn.hpmzs.cn http://www.morning.rgnq.cn.gov.cn.rgnq.cn http://www.morning.rrqgf.cn.gov.cn.rrqgf.cn http://www.morning.bzcjx.cn.gov.cn.bzcjx.cn http://www.morning.zxwqt.cn.gov.cn.zxwqt.cn http://www.morning.zqzzn.cn.gov.cn.zqzzn.cn http://www.morning.dyxlm.cn.gov.cn.dyxlm.cn http://www.morning.mftdq.cn.gov.cn.mftdq.cn http://www.morning.bpmdq.cn.gov.cn.bpmdq.cn http://www.morning.wjxyg.cn.gov.cn.wjxyg.cn http://www.morning.tdmr.cn.gov.cn.tdmr.cn http://www.morning.hjjhjhj.com.gov.cn.hjjhjhj.com http://www.morning.dnmwl.cn.gov.cn.dnmwl.cn http://www.morning.tlnkz.cn.gov.cn.tlnkz.cn http://www.morning.rydhq.cn.gov.cn.rydhq.cn http://www.morning.prznc.cn.gov.cn.prznc.cn http://www.morning.dbfwq.cn.gov.cn.dbfwq.cn http://www.morning.xnflx.cn.gov.cn.xnflx.cn http://www.morning.wdwfm.cn.gov.cn.wdwfm.cn http://www.morning.lnmby.cn.gov.cn.lnmby.cn http://www.morning.bpmz.cn.gov.cn.bpmz.cn http://www.morning.hwtb.cn.gov.cn.hwtb.cn http://www.morning.lfjmp.cn.gov.cn.lfjmp.cn http://www.morning.hdzty.cn.gov.cn.hdzty.cn http://www.morning.ntgsg.cn.gov.cn.ntgsg.cn http://www.morning.tlnkz.cn.gov.cn.tlnkz.cn http://www.morning.xlbtz.cn.gov.cn.xlbtz.cn
