【leetcode】动态规划::前缀和(二)

这篇具有很好参考价值的文章主要介绍了【leetcode】动态规划::前缀和(二)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

标题:【leetcode】前缀和(二)

@水墨不写bug

【leetcode】动态规划::前缀和(二),决胜oj,leetcode,数据结构,算法,动态规划,c++


 正文开始:

(一) 和为K的子数组

给你一个整数数组 nums 和一个整数 k ,请你统计并返回 该数组中和为 k 的子数组的个数 

子数组是数组中元素的连续非空序列。

示例 1:

输入:nums = [1,1,1], k = 2
输出:2

示例 2:

输入:nums = [1,2,3], k = 3
输出:2

提示:

  • 1 <= nums.length <= 2 * 10^4
  • -1000 <= nums[i] <= 1000
  • -10^7 <= k <= 10^7

 思路一:

        暴力求解,按照题目的描述来求解,对于每一个数,依次向后求和,如果和==k,此时不能停下来,ret++继续遍历到整个数组。很显然,此算法时间复杂度O(N^2),显然是会超时的算法。

思路二:

        我们可以换一种思路,现在我们聚焦于以下标 i 为结尾的和为k的数组,它们可能存在一个或者多个,甚至根本不存在;这时,我们已经固定了一个下标i,只需找到另一个下标即可;假设 i 之前存在一个下标 i0,[ i0 , i ](闭区间)的区间和为 k ,这时算出 以 i 为结尾的前缀和 sum[i],这就将问题:i之前是否存在i0,使得[ i0 , i ](闭区间)的区间和为 k —转化为了—> 下标 i 之前是否存在 i0 使得 i0 的前缀和为 sum[i] - k;

        这时如果你就按照以上思路来建立前缀和数组,然后使用数组时你就会后悔自己做过的事情了:在使用前缀和数组的时候,对于一个指针cur = i,需要向前遍历数组,在cur向后移动后,还要进行向前遍历,这个操作的时间复杂度为O(N^2),再加上建立前缀和数组的O(N),时间复杂度不减反增!

        这时我们就需要考虑,一些操作是否能够同时进行:将for的嵌套优化为一个for循环即可解决的问题。

        如何理解呢,其实一些互不影响的操作可以可以同时进行,这时我们就可以在同一个循环中同时进行多个操作,以此来减少for循环的个数,以此来降低时间复杂度。

        在本题中,由于前缀和前n项和在每次循环中只使用一次,所以可以创建一个变量,通过对变量进行迭代累加求和,来代替前缀和数组。

        sum是不断变化的,此时创建一个哈希表,目的是用来记录此时sum的值,在向后遍历时,sum会递增。

        创建变量ret累计和为k的字符串的个数;

        sum记录第i项的前缀和;

        创建hash表,用来向前找(sum-k)时 ret 累加 答案(sum-k)的个数。

参考代码: 

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int,int> hash;
        int ret = 0,sum = 0;
        hash[0] = 1;
        for(auto x:nums)
        {
            sum+=x;
            if(hash.count(sum-k)) ret += hash[sum-k];
            hash[sum]++;
        }
        return ret;
    }
};

(二)可被K整除的子数组

给定一个整数数组 nums 和一个整数 k ,返回其中元素之和可被 k 整除的(连续、非空) 子数组 的数目。

子数组 是数组的 连续 部分。

示例 1:

输入:nums = [4,5,0,-2,-3,1], k = 5
输出:7
解释:
有 7 个子数组满足其元素之和可被 k = 5 整除:
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

示例 2:

输入: nums = [5], k = 9
输出: 0

提示:

  • 1 <= nums.length <= 3 * 10^4
  • -10^4 <= nums[i] <= 10^4
  • 2 <= k <= 10^4

在解决本题之前,需要知道:

(1)同余定理

        如果(a - b) % n == 0 ,那么我们可以得到⼀个结论: a % n == b % n 。文字叙
述就是,如果两个数相减的差能被n整除,那么这两个数对n取模的结果相同。

(2)c++ 中负数取模的结果,以及如何修正「负数取模」的结果

        c++ 中关于负数的取模运算,结果是「把负数当成正数,取模之后的结果加上⼀个负号」。


例如: -2 % 3 = -(2 % 3) = -2


        因为有负数,为了防止发生「出现负数」的结果,以 (a % n + n) % n 的形式输出保证为正。


例如: -2 % 3 = (-2 % 3 + 3) % 3 = 1

此外,本题的思路和  560.和为K的子数组  这道题的思路相似。

        设 i 为数组中的任意位置,用  sum[i]  表示  [0, i]  区间内所有元素的和。
        想知道有多少个「以 i 为结尾的可被 k 整除的子数组」,就要找到有多少个起始位置为 x1,x2, x3... 使得 [x, i] 区间内的所有元素的和可被 k 整除。

  •  设 [0, x - 1] 区间内所有元素之和等于 a , [0, i] 区间内所有元素的和等于 b ,可得(b - a) % k == 0 。
  •  由同余定理可得, [0, x - 1] 区间与 [0, i] 区间内的前缀和同余。于是问题就变成:找到在 [0, i - 1] 区间内,有多少前缀和的余数等于 sum[i] % k 的即可。

        我们不用真的初始化⼀个前缀和数组,因为我们只关心在 i 位置之前,有多少个前缀和等于sum[i] - k 。因此,我们仅需用⼀个哈希表,一边求当前位置的前缀和,⼀边存下之前每⼀种前缀和出现的次数。

参考代码: 

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        unordered_map<int,int> hash;
        hash[0%k] = 1;
        int sum = 0,ret = 0;
        for(const auto& e : nums)
        {
            sum += e;//计算前缀和
            //判断是否有符合要求的前缀和
            int aim = (sum%k+k)%k;
           if(hash.count(aim)) ret += hash[aim];
           hash[aim]++;
        }
        return ret;
    }
};

(三)连续数组

给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组,并返回该子数组的长度。

示例 1:

输入: nums = [0,1]
输出: 2
说明: [0, 1] 是具有相同数量 0 和 1 的最长连续子数组。

示例 2:

输入: nums = [0,1,0]
输出: 2
说明: [0, 1] (或 [1, 0]) 是具有相同数量0和1的最长连续子数组。

提示:

  • 1 <= nums.length <= 10^5
  • nums[i] 不是 0 就是 1

         这道题看似复杂,其实它就是   560.和为K的子数组 的特殊情况:

        题目要求我们找出一段连续的区间,满足0和1出现的次数相同。

        如果遍历区间,遇 0 就自减,遇 1 不操作。

        则这道题就变成了:找出一段区间,并使区间的和等于0;

        那么就和 560.和为K的子数组 思路相同了。

参考代码: 

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        unordered_map<int,int> hash;//存前缀和与对应的下标
        hash[0] = -1;
        for( auto& e:nums) if(e == 0) e--;
        int ret = 0,sum = 0,n = nums.size();
        for(int i = 0;i < n;i++)
        {
            sum += nums[i];
            if(hash.count(sum)) ret = max(ret,i-hash[sum]);
            else hash[sum] = i;
        }
        return ret;
    }
};

完~

未经作者同意禁止转载文章来源地址https://www.toymoban.com/news/detail-857304.html

到了这里,关于【leetcode】动态规划::前缀和(二)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【LeetCode】【数据结构】单链表OJ常见题型(一)

     👀 樊梓慕: 个人主页   🎥 个人专栏: 《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》 🌝 每一个不曾起舞的日子,都是对生命的辜负。 目录 前言: 【LeetCode】203.移除链表元素 【LeetCode】206.反转链表  思路一 思路二 【LeetCode】876.链表的中间结点 快慢指针法

    2024年02月14日
    浏览(37)
  • 【LeetCode】【数据结构】单链表OJ常见题型(二)

     👀 樊梓慕: 个人主页   🎥 个人专栏: 《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》 🌝 每一个不曾起舞的日子,都是对生命的辜负 目录 前言: 【LeetCode】面试题02.04. 分割链表 【LeetCode】160. 相交链表 【LeetCode】141. 环形链表 【LeetCode】142. 环形链表Ⅱ 方法

    2024年02月14日
    浏览(41)
  • 【LeetCode】【数据结构】二叉树必刷OJ题

    👀 樊梓慕: 个人主页   🎥 个人专栏: 《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》 🌝 每一个不曾起舞的日子,都是对生命的辜负 目录 前言 【LeetCode】226.翻转二叉树 【LeetCode】100.相同的树 【LeetCode】5.对称二叉树 【LeetCode】9.另一颗树的子树

    2024年02月08日
    浏览(49)
  • 【LeetCode】【数据结构】栈与队列必刷OJ题

    👀 樊梓慕: 个人主页   🎥 个人专栏: 《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》 🌝 每一个不曾起舞的日子,都是对生命的辜负 目录 前言: 【LeetCode】20.有效的括号(栈的括号匹配问题) 【LeetCode】225.用队列实现栈 【LeetCode】232.用栈实现队列 【LeetCo

    2024年02月13日
    浏览(42)
  • LeetCode 2811. Check if it is Possible to Split Array【脑筋急转弯;前缀和+动态规划或记忆化DFS】中等

    本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章中,我不仅会讲解多种解题思路及其优化,

    2024年02月13日
    浏览(32)
  • 数据结构:带环单链表基础OJ练习笔记(leetcode142. 环形链表 II)(leetcode三题大串烧)

    目录 一.前言  二.leetcode160. 相交链表  1.问题描述 2.问题分析与求解 三.leetcode141. 环形链表 1.问题描述 2.代码思路  3.证明分析  下一题会用到的重要小结论: 四.leetcode142. 环形链表 II 1.问题描述 2.问题分析与求解 Judgecycle接口: 方法一: 方法二:  单链表和带环单链表

    2023年04月08日
    浏览(37)
  • 数据结构之---- 动态规划

    动态规划是一个重要的算法范式,它将一个问题分解为一系列更小的子问题,并通过存储子问题的解来避免重复计算,从而大幅提升时间效率。 在本节中,我们从一个经典例题入手,先给出它的暴力回溯解法,观察其中包含的重叠子问题,再逐步导出更高效的动态规划解法。

    2024年02月04日
    浏览(41)
  • 数据结构与算法-动态规划

    (我猜是做的多了背的题多了就自然懂了) 迭代法一般没有通用去重方式,因为已经相当于递归去重后了 这两个问题其实是一个问题,一般直接写出的没有去重的递归法,复杂度很高,此时需要使用备忘录去重,而备忘录去重时间复杂度和使用dp数组进行迭代求解时间复杂度相同

    2024年02月04日
    浏览(43)
  • 前缀和算法(类似于动态规划算法)

    前缀和:在一些特定的题里面,要先把 一段连续的数的和 先算出来,用 数组来接收 ,然后 利用这个数组 返回题目需要的答案 干讲无力 题目解释更好 请往下看 题目:题目链接 题目解析: 在数组中找到一个下标,划分为2个区间 左区间的和=右区间的和,如果没有这个下标则返

    2024年02月04日
    浏览(33)
  • python算法与数据结构---动态规划

    记不住过去的人,注定要重蹈覆辙。 对于一个模型为n的问题,将其分解为k个规模较小的子问题(阶段),按顺序求解子问题,前一子问题的解,为后一子问题提供有用的信息。在求解任一子问题时,通过决策求得局部最优解,依次解决各子问题。最后通过简单的判断,得到

    2024年02月20日
    浏览(65)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包