当前位置: 首页 > news >正文

驻马店公司做网站深圳百度推广关键词推广

驻马店公司做网站,深圳百度推广关键词推广,学java哪个培训学校最好,招聘网站建设方案题目 链接:leetcode链接 思路分析(前缀和 同余定理) 首先,我们要了解一下什么是同余定理 同余定理: 如果(a - b)/ p k …… 0 则 a % p b % p 证明我写在草稿纸上,如下图: 初…

题目

链接:leetcode链接

在这里插入图片描述

思路分析(前缀和 + 同余定理)

首先,我们要了解一下什么是同余定理

同余定理:
如果(a - b)/ p = k …… 0
则 a % p == b % p

证明我写在草稿纸上,如下图:
在这里插入图片描述

初此之外,我们还需要理解一个问题
在C++/java中负数取模会怎么样呢?
比如 - 2 % 5等于多少呢?
按道理来说应该是3,但是C++/java里的答案是-2
这明显是需要进行修正的

如何进行修正呢?
我们只需要( a % p + p)% p
这样,无论是正数取模还是负数取模都不会出现问题。

OK,到这里前置知识讲完了,我们就正式开始讲思路了。

需要找一个子数组的和是k的倍数
那么只需要找两个区间的前缀和对k取模的余数相同即可。

和这道题的思路非常相似
传送门:560.和为k的子数组

我们利用滚动数组去求前缀和,
记录sum % k的余数
然后在[0,i-1]区间内去hash表中寻找一个区间的前缀和对k取模的结果与sum对k取模结果相同即可
将sum% k的余数放到hash表中(一定要是先查找在插入)

细节:
(1)什么时候插入hash表
一定要是先查找,在插入
(2)对于[0 , i]区间的和正好是K的倍数的情况如何处理
还是一样,我们先去把余数0提前先往hash表里插一个即可
具体原因可以查看和为k的子数组这篇文章

代码

//同余定理int subarraysDivByK(vector<int>& nums, int k) {int sum = 0,ret = 0;unordered_map<int,int> hash;//hash表里面放余数hash[0] = 1;//这个0依旧是存的余数for(auto& e:nums){sum += e;int check = (sum % k + k) % k; // 对余数进行修正很关键if(hash.count(check))  ret += hash[check]; hash[check]++;}return ret;}
http://www.15wanjia.com/news/18074.html

相关文章:

  • 网站图片内容免费视频网站推广软件
  • dedecms 迁移 wordpressseo关键词教程
  • 网站外部外链建设个人网站设计毕业论文
  • 浙江人工智能建站系统软件百度广告收费表
  • 如何自己建设网站石家庄热搜
  • 网站建设源码网站制作建设
  • 云主题 wordpress深圳关键词优化公司哪家好
  • 泉州企业网站开发网络营销的四大基础理论
  • 个人免费网站如何做深圳推广公司
  • 做家乡网站seo的内容主要有哪些方面
  • 行业网站怎么建设关联词有哪些 全部
  • 怎么做网站关键词排名备案域名交易平台
  • 短视频拍摄培训班企业seo推广
  • 网站开发设计说明书推广自己的网站
  • 京东商城网官网广州seo推广服务
  • 北京市网站备案查询南京seo排名优化公司
  • 教育门户网站系统建设方案百度推广渠道商
  • 400全国服务热线佛山手机网站建设提升关键词
  • 帝国网站程序磁力天堂最佳搜索引擎入口
  • 医疗网站优化怎么做成都专业seo公司
  • 网站开发系统规划打开官方网站
  • 现在手机网站用什么做的搜索app下载安装
  • 购物网站首页界面设计vi设计公司
  • 网站建设总计公关公司一般收费标准
  • 福州 网站建设长春网站建设团队
  • 郑州做网站推广的公司哪家好镇江seo
  • phpstudy建wordpress网站的seo优化报告
  • 网站建设应注意哪些事项百度搜索平台
  • 优化网站被百度屏厦门seo厦门起梦
  • dede怎么设置wap网站网络推广员工资多少钱