LeetCode523. 连续的子数组和

2021-03-17 15:24

阅读：409

标签：表示 for false loading int ++i solution 预处理 lse

技术图片

因为子数组是连续的，所以判断连续的子数组的和时，我们往往开一个前缀和数组预处理出所有数的前缀和，这样能够降低求子数组的和的时间复杂度。

这题需要单独处理k为0的情况，由于数组所有元素都是非负数，所以当k为0时，如果存在两个相邻的数的值都为0，则返回true，否则返回false。

使用前缀和判断是否存在满足条件的子数组时，只需从小到大枚举子数组的长度，然后再在内层循环内枚举子数组的长度，然后使用前缀和计算区间和的公式计算是否存在子数组的和满足条件即可。有点类似区间dp，hh。

代码如下：

class Solution {
public:
    bool checkSubarraySum(vector& nums, int k) {
        int n = nums.size();
        if(k == 0) {
            for(int i = 0; i  preSum(n + 1, 0);                  // preSum是前缀和, preSum[i]表示nums[0] + nums[1] + ... + nums[i - 1]
        for(int i = 1; i

LeetCode523. 连续的子数组和

标签：表示 for false loading int ++i solution 预处理 lse

原文地址：https://www.cnblogs.com/linrj/p/13972737.html

上一篇：C# 泛型集合的自定义类型排序

下一篇：javascript: 一个可以代替jquery选择器的方法

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：LeetCode523. 连续的子数组和
文章链接：http://soscw.com/index.php/essay/65355.html

亲，登录后才可以留言！

LeetCode523. 连续的子数组和

评论

热门文章

推荐文章

最新文章

置顶文章