523 Continuous Subarray Sum 非负数组中找到和为K的倍数的连续子数组
2024-08-24 07:49:49
非负数组中找到和为K的倍数的连续子数组
详见：https://leetcode.com/problems/continuous-subarray-sum/description/
Java实现：
方法一：
class Solution {
public boolean checkSubarraySum(int[] nums, int k) {
for(int i=0;i<nums.length;++i){
int sum=nums[i];
for(int j=i+1;j<nums.length;++j){
sum+=nums[j];
if(sum==k){
return true;
}
if(k!=0&&sum%k==0){
return true;
}
}
}
return false;
}
}
方法二：
class Solution {
public boolean checkSubarraySum(int[] nums, int k) {
if(nums==null){
return false;
}
HashSet<Integer> sums=new HashSet<>();
int sum=0;
for(int i=0;i<nums.length;++i){
sum+=nums[i];
if((k!=0&&sums.contains(sum%k))||(i!=0&&sum==k)){
return true;
}else if(k!=0){
sums.add(sum%k);
}
}
return false;
}
}
方法三：用HashMap保存sum对k取余数，如果前序有余数也为sum%k的位置，那么就存在连续子数组和为k的倍数。
class Solution {
public boolean checkSubarraySum(int[] nums, int k) {
Map<Integer,Integer> map=new HashMap<Integer,Integer>(){{put(0,-1);}};
int sum=0;
for(int i=0;i<nums.length;++i){
sum+=nums[i];
if(k!=0){
sum%=k;
}
Integer prev=map.get(sum);
if(prev!=null){
if(i-prev>1){
return true;
}
}else{
map.put(sum,i);
}
}
return false;
}
}
C++：
方法一：
class Solution {
public:
bool checkSubarraySum(vector<int>& nums, int k)
{
for (int i = 0; i < nums.size(); ++i)
{
int sum = nums[i];
for (int j = i + 1; j < nums.size(); ++j)
{
sum += nums[j];
if (sum == k)
{
return true;
}
if (k != 0 && sum % k == 0)
{
return true;
}
}
}
return false;
}
};
方法二：
class Solution {
public:
bool checkSubarraySum(vector<int>& nums, int k)
{
int n = nums.size(), sum = 0, pre = 0;
unordered_set<int> st;
for (int i = 0; i < n; ++i)
{
sum += nums[i];
int t = (k == 0) ? sum : (sum % k);
if (st.count(t))
{
return true;
}
st.insert(pre);
pre = t;
}
return false;
}
};
参考：http://www.cnblogs.com/grandyang/p/6504158.html
最新文章
- Git各大平台（win／Linux／Mac）图形化界面客户端大汇总
- sys
- rt—移植笔记1
- 开发《基于Arcgis Online的家政管理服务信息系统》随笔2
- Problem 1274 - 可怜的lpx
- PHP页面静态化入门
- web字体格式及几种在线格式转换工具介绍
- VS的工程宏，比如$(SolutionDir) 的含义及查找
- MAC apache 2.4 启用目录访问
- Javascript闭包（Closure）
- 【原创】大数据基础之Logstash（4）高可用
- sqlServer：行列转换之多行转一行
- react-navigation 简介
- 结对编程ending-我和洧洧的碎碎念
- Halcon知识点随记（每日更新）
- Scrapy 框架 使用 selenium 爬取动态加载内容
- BZOJ3286 Fibonacci矩阵 矩阵 快速幂 卡常
- DFS例题
- sun.misc.BASE64Decoder 限制取消
- Python图形编程探索系列-07-程序登录界面设计
热门文章
- 赵雅智_SimpleCursorAdapter
- leetcode笔记：Pascal&#39;s Triangle
- java8--面向对象 上（疯狂java讲义3） 复习笔记
- Writing a Discard Server
- python 1: 解决linux系统下python中的matplotlib模块内的pyplot输出图片不能显示中文的问题
- POJ2155 Matrix 二维线段树
- CWnd中PreCreateWindow、PreSubclassWindow、SubclassWindow
- ossfs常见配置错误
- Why you shouldn’t connect your mobile application to a database
- 关于O_DIRECT的那些事儿