523. 连续的子数组和

柔情只为你懂 2022-10-17 10:43 127阅读 0赞

给你一个整数数组 nums 和一个整数 k ，编写一个函数来判断该数组是否含有同时满足下述条件的连续子数组：

子数组大小 至少为 2 ，且  
子数组元素总和为 k 的倍数。  
如果存在，返回 true ；否则，返回 false 。

如果存在一个整数 n ，令整数 x 符合 x = n \* k ，则称 x 是 k 的一个倍数。

示例 1：

输入：nums = \[23,2,4,6,7\], k = 6  
输出：true  
解释：\[2,4\] 是一个大小为 2 的子数组，并且和为 6 。  
示例 2：

输入：nums = \[23,2,6,4,7\], k = 6  
输出：true  
解释：\[23, 2, 6, 4, 7\] 是大小为 5 的子数组，并且和为 42 。   
42 是 6 的倍数，因为 42 = 7 \* 6 且 7 是一个整数。  
示例 3：

输入：nums = \[23,2,6,4,7\], k = 13  
输出：false

提示：

1 <= nums.length <= 105  
0 <= nums\[i\] <= 109  
0 <= sum(nums\[i\]) <= 231 - 1  
1 <= k <= 231 - 1

class Solution {
    public:
        bool checkSubarraySum(vector<int>& nums, int k) {
            //双指针是不可行的，因为大于k时不一定是错误的选择，可能通过取余产生新的模
            set<int> se;
            int s = 0;
            se.insert(0);
            for(int i = 0;i<nums.size();i++)
            {
                if(i+1<nums.size()&&(nums[i]+nums[i+1])%k==0) return true;
                if(nums[i]%k==0) continue;
                s=(s+nums[i])%k;
                if(se.count(s))
                {
                    return true;
                }
                se.insert(s);
            }
            return false;
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，127人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode_前缀和_哈希表_中等_523.连续的子数组和

目录 1.题目 2.思路 3.代码实现（Java） 1.题目给你一个整数数组 nums 和一个整数 k ，编写一个函数来判断该数组是否含有同时

一时失言乱红尘/ 2023年10月06日 23:21/ 0 赞/ 7 阅读

相关 523. 连续的子数组和

> 给你一个整数数组 nums 和一个整数 k ，编写一个函数来判断该数组是否含有同时满足下述条件的连续子数组： > > 子数组大小至少为 2 ，且 > 子数组元素总和

拼搏现实的明天。/ 2022年10月18日 11:23/ 0 赞/ 129 阅读

相关 523. 连续的子数组和

2021-06-02 LeetCode每日一题链接：[https://leetcode-cn.com/problems/continuous-subarray-sum/

末蓝、/ 2022年10月17日 11:14/ 0 赞/ 148 阅读

相关 523. 连续的子数组和

给你一个整数数组 nums 和一个整数 k ，编写一个函数来判断该数组是否含有同时满足下述条件的连续子数组：子数组大小至少为 2 ，且子数组元素总和为 k 的倍数。

柔情只为你懂/ 2022年10月17日 10:43/ 0 赞/ 128 阅读

相关连续子数组的最大和

HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。

短命女/ 2022年09月25日 12:19/ 0 赞/ 226 阅读

相关 leetcode 523. Continuous Subarray Sum | 523. 连续的子数组和（同余定理）

题目 [https://leetcode.com/problems/continuous-subarray-sum/][https_leetcode.com_proble

快来打我*/ 2022年09月12日 05:52/ 0 赞/ 192 阅读

相关 523 连续的子数组和（枚举、前缀和、哈希表）

1. 问题描述：给你一个整数数组 nums 和一个整数 k ，编写一个函数来判断该数组是否含有同时满足下述条件的连续子数组：子数组大小至少为 2 ，且子数组元素总和为

秒速五厘米/ 2022年08月30日 05:15/ 0 赞/ 177 阅读

相关最大连续子数组和

最大连续子数组和 1. 题目描述输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有

快来打我*/ 2022年08月06日 01:06/ 0 赞/ 207 阅读

相关连续子数组的最大和

虽然在剑指offer上看到过，在真正做这道题的时候才发现自己的不足在线判题传送门： [点这里][Link 1] 题目：一个数组有 N 个元素，求连续子数组的

￡神魔★判官ぃ/ 2022年06月09日 03:37/ 0 赞/ 193 阅读

相关连续子数组的最大和

题目描述 HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候

小灰灰/ 2022年05月14日 09:14/ 0 赞/ 223 阅读