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

力扣刷题-数组-滑动窗口法相关题目总结

209. 长度最小的子数组(最小滑窗)

给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组,并返回其长度。如果不存在符合条件的子数组,返回 0。
示例:
输入:s = 7, nums = [2,3,1,2,4,3]
输出:2
解释:子数组 [4,3] 是该条件下的长度最小的子数组。
注意题目是返回长度即可。

暴力法

class Solution(object):def minSubArrayLen(self, target, nums):""":type target: int:type nums: List[int]:rtype: int"""## 难的问题 可以先考虑暴力解法(若没有要求时间复杂度)min_len = float('inf') # 先定义一个无穷大 min_len 后续再迭代更新for i in range(len(nums)):sum = 0for j in range(i, len(nums)):sum += nums[j]if sum >= target:min_len = min(min_len, j-i+1)break # 使用break 防止再遍历下去return min_len if min_len != float('inf') else 0

时间复杂度:O(n^2)
空间复杂度:O(1)
image.png

滑动窗口法

接下来就开始介绍数组操作中另一个重要的方法:滑动窗口。
所谓滑动窗口,就是不断的调节子序列的起始位置和终止位置,从而得出我们要想的结果。
在暴力解法中,是一个for循环滑动窗口的起始位置,一个for循环为滑动窗口的终止位置,用两个for循环 完成了一个不断搜索区间的过程。
那么滑动窗口如何用一个for循环来完成这个操作呢。
首先要思考 如果用一个for循环,那么应该表示 滑动窗口的起始位置,还是终止位置。
如果只用一个for循环来表示 滑动窗口的起始位置,那么如何遍历剩下的终止位置?
此时难免再次陷入 暴力解法的怪圈。
所以 只用一个for循环,那么这个循环的索引,一定是表示 滑动窗口的终止位置。
那么问题来了, 滑动窗口的起始位置如何移动呢?
这里还是以题目中的示例来举例,s=7, 数组是 2,3,1,2,4,3,来看一下查找的过程:

其实从动画中可以发现滑动窗口也可以理解为双指针法的一种!只不过这种解法更像是一个窗口的移动,所以叫做滑动窗口更适合一些。
在本题中实现滑动窗口,主要确定如下三点:

  • 窗口内是什么?
  • 如何移动窗口的起始位置?
  • 如何移动窗口的结束位置?

窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。
窗口的起始位置如何移动:如果当前窗口的值大于s了,窗口就要向前移动了(也就是该缩小了)。
窗口的结束位置如何移动:窗口的结束位置就是遍历数组的指针,也就是for循环里的索引。
解题的关键在于 窗口的起始位置如何移动,如图所示:
image.png
可以发现滑动窗口的精妙之处在于根据当前子序列和大小的情况,不断调节子序列的起始位置。从而将O(n^2)暴力解法降为O(n)。

class Solution(object):def minSubArrayLen(self, target, nums):""":type target: int:type nums: List[int]:rtype: int"""min_len = float("inf") # 同样也是先初始化一个min_leni, sum = 0, 0for j in range(len(nums)):sum += nums[j]while sum >= target:min_len = min(min_len, j-i+1)sum -= nums[i]i += 1 # 这两行是滑动窗口的巧妙之处return min_len if min_len != float("inf") else 0

区分时间复杂度:
暴力解题法:O(n^2) 因为第一个for循环在第一个元素的时候,第二个for循环会遍历所有元素;第一个for循环在第二个元素的时候也会遍历在第二个for循环的时候遍历所有元素…)——> n*n=n^2
滑动窗口法:不要以为for里放一个while就以为是O(n^2)啊, 主要是看每一个元素被操作的次数,每个元素在滑动窗后进来操作一次,出去操作一次,每个元素都是被操作两次,所以时间复杂度是 2 × n 也就是O(n)。
子串问题优先滑动窗口。

滑动窗口法模板

一般什么时候会考虑使用 滑动窗口法 ?——>答:当求子串问题(最小长度/最大长度,对应最小滑窗/最大滑窗)时候常常考虑使用滑动窗口法。 若需要种类计数,记得定义一个种类计数器以及种类计数
参考:
作者:HelloPGJC
链接:https://leetcode.cn/problems/fruit-into-baskets/solutions/1437444/shen-du-jie-xi-zhe-dao-ti-he-by-linzeyin-6crr/
来源:力扣(LeetCode)

最小滑窗

最小滑窗模板:给定数组 nums,定义滑窗的左右边界 i, j,求满足某个条件的滑窗的最小长度。

while j < len(nums):判断[i, j]是否满足条件(如果是简单的 一般不需要判断条件 如上面的题)while 满足条件:不断更新结果(注意在while内更新!所谓结果就是求的长度)i += 1 (最大程度的压缩i,使得滑窗尽可能的小)j += 1
最大滑窗

最大滑窗模板:给定数组 nums,定义滑窗的左右边界 i, j,求满足某个条件的滑窗的最大长度。

while j < len(nums):判断[i, j]是否满足条件while 不满足条件:i += 1 (最保守的压缩i,一旦满足条件了就退出压缩i的过程,使得滑窗尽可能的大)不断更新结果(注意在while外更新!)j += 1

如上面的题:

class Solution(object):def minSubArrayLen(self, target, nums):""":type target: int:type nums: List[int]:rtype: int"""min_len = float("inf") # 同样也是先初始化一个min_leni, sum = 0, 0for j in range(len(nums)):sum += nums[j]while sum >= target:min_len = min(min_len, j-i+1)sum -= nums[i]i += 1 # 这两行是滑动窗口的巧妙之处return min_len if min_len != float("inf") else 0

76. 最小覆盖子串(最小滑窗)

题目难度:困难
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 “” 。
注意:

  • 对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
  • 如果 s 中存在这样的子串,我们保证它是唯一的答案。

示例 1:
输入:s = “ADOBECODEBANC”, t = “ABC”
输出:“BANC”
解释:最小覆盖子串 “BANC” 包含来自字符串 t 的 ‘A’、‘B’ 和 ‘C’。
示例 2:
输入:s = “a”, t = “a”
输出:“a”
解释:整个字符串 s 是最小覆盖子串。
示例 3:
输入: s = “a”, t = “aa”
输出: “”
解释: t 中两个字符 ‘a’ 均应包含在 s 的子串中,
因此没有符合条件的子字符串,返回空字符串。
求最小子串问题——>滑动窗口法
解析题意:
最小字串——>滑动窗口法
找出的s的子串需要涵盖t中的字符——>会使用字典计数器

class Solution(object):def minWindow(self, s, t):""":type s: str:type t: str:rtype: str"""i, j = 0, 0needMap = defaultdict(int) # 定义一个字典计数器(对字符, 初始化都是0)needCnt = len(t) # 最开始 在s中我需要涵盖的字符数就是t中总的字符数res = "" # 结果 初始化为 ""for c in t:needMap[c] += 1 # 为字符计数器赋值while j < len(s):if s[j] in needMap:if needMap[s[j]] > 0:needCnt -= 1 # 有这个字符 那么我需要的字符数就减1needMap[s[j]] -= 1 # 因为t中可能有重复字符 所以这个需要减1while needCnt == 0:if not res or j-i+1 < len(res): # res为空(前面没有结果) 注意是小于len(res) 因为是最小子串res = s[i:j+1] # 获取# 上面只是更新了结果 needMap和needCnt还没有更新if s[i] in needMap:if needMap[s[i]] == 0:needCnt += 1 # 因为我下一步要移动i 所以如果现在没有这个字符 我需要的字符数加1needMap[s[i]] += 1 # 因为我下一步要移动i 所以如果现在没有这个字符 就要加1 告诉后面我需要i += 1 # 更新 ij += 1 # 更新jreturn res

904. 水果成篮(最大字串)

你正在探访一家农场,农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示,其中 fruits[i] 是第 i 棵树的种类 。
你想要尽可能多地收集水果。然而,农场的主人设定了一些严格的规矩,你必须按照要求采摘水果:
你只有 两个 篮子,并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
你可以选择任意一棵树开始采摘,你必须从 每棵 树(包括开始采摘的树)上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次,你将会向右移动到下一棵树,并继续采摘。
一旦你走到某棵树前,但水果不符合篮子的水果类型,那么就必须停止采摘。
给你一个整数数组 fruits ,返回你可以收集的水果的 最大 数目。
解题:
像这种就需要先翻译一下题目意思,就是让你从一个整数数组中,找出其中最长的子数组,然后一个限制条件是,这个最长子数组中的整数最多只能有两种。
本题返回的是子数组长度,不是子数组,注意分清楚
示例 1:
输入:fruits = [1,2,1]
输出:3
解释:可以采摘全部 3 棵树。
示例 2:
输入:fruits = [0,1,2,2]
输出:3
解释:可以采摘 [1,2,2] 这三棵树。
如果从第一棵树开始采摘,则只能采摘 [0,1] 这两棵树。
示例 3:
输入:fruits = [1,2,3,2,2]
输出:4
解释:可以采摘 [2,3,2,2] 这四棵树。
如果从第一棵树开始采摘,则只能采摘 [1,2] 这两棵树。

class Solution(object):def totalFruit(self, fruits):""":type fruits: List[int]:rtype: int"""# 初始化i, j = 0, 0res = 0 # 要求最大 我先初始化为0classMap = defaultdict(int) # 因为涉及到种类数 所以需要一个种类计数器classCnt = 0 # 因为是求最大 我刚开始计数当然为0while j < len(fruits):if classMap[fruits[j]] == 0:classCnt += 1 # 第一个数 种类肯定是加1classMap[fruits[j]] += 1while classCnt > 2: # 不符合条件 种类数超过2# if classMap[fruits[i]] > 0: # 不能用0判断 因为不知道种类数能不能减1if classMap[fruits[i]] == 1:classCnt -= 1 # 因为下一步我就要移动i了, 当前为1 移动一下肯定为0classMap[fruits[i]] -= 1 # 该种类数计数也减1i += 1res = max(res, j-i+1) # 在while外面更新结果j += 1return res

理解最小滑窗和最大滑窗的更新的不同之处:
image.png
因为是符合条件才更新结果,最小滑动窗口中,while的条件是 满足条件 因此在while内更新,而最大滑动窗口中,while的条件是 不满足条件 因此得等到条件满足,也就是退出循环后再更新

1004. 最大连续1的个数 III

给定一个二进制数组 nums 和一个整数 k,如果可以翻转最多 k 个 0 ,则返回 数组中连续 1 的最大个数 。
示例 1:
输入:nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出:6
解释:[1,1,1,0,0,1,1,1,1,1,1]
粗体数字从 0 翻转到 1,最长的子数组长度为 6。
示例 2:
输入:nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
输出:10
解释:[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
粗体数字从 0 翻转到 1,最长的子数组长度为 10。
注意,要理清题意,这里未涉及种类计数,其中 条件 就是 0的数量 因为翻转0是题目已经设定好的。

class Solution(object):def longestOnes(self, nums, k):""":type nums: List[int]:type k: int:rtype: int"""# 求数组中的子数组 最大个数 ——> 最大滑窗# 限制条件是 最大翻转k个0 需要0的个数# 想复杂了 还是要理清题意i, j = 0, 0res = 0zeroCnt = 0while j < len(nums):if nums[j] == 0:zeroCnt += 1while zeroCnt > k: # 注意是kif nums[i] == 0:zeroCnt -= 1 # 因为我下一步要移动ii += 1res = max(res, j-i+1)j += 1return res 

3. 无重复字符的最长子串

给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。
示例 2:
输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”,所以其长度为 1。
示例 3:
输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”,所以其长度为 3。
请注意,你的答案必须是 子串 的长度,“pwke” 是一个子序列,不是子串。

class Solution(object):def lengthOfLongestSubstring(self, s):""":type s: str:rtype: int"""# 子串 最大长度 ——> 最大滑窗# 不含重复字符 说明遇到字符计数# 巧妙之处:将子串中的字符数 与 字典长度联系起来# 模板不要用的太死板i, j = 0, 0res = 0char_dict = defaultdict(int)while j < len(s):char_dict[s[j]] += 1while len(char_dict)<j-i+1: # 不满足条件 这个比较难想char_dict[s[i]] -= 1 # 下一步就是移动iif char_dict[s[i]] == 0:del char_dict[s[i]]i += 1if len(char_dict) == j - i + 1:  # 巧妙之处res = max(res, j-i+1)j+=1return res

参考:https://programmercarl.com/

相关文章:

力扣刷题-数组-滑动窗口法相关题目总结

209. 长度最小的子数组&#xff08;最小滑窗&#xff09; 给定一个含有 n 个正整数的数组和一个正整数 s &#xff0c;找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组&#xff0c;并返回其长度。如果不存在符合条件的子数组&#xff0c;返回 0。 示例&#xff1a; 输入&…...

Qt创建线程(线程池)

1.线程池可以创建线程统一的管理线程&#xff08;统一创建、释放线程&#xff09; 2.使用线程池方法实现点击开始按钮生成10000个随机数&#xff0c;然后分别使用冒泡排序和快速排序排序这10000个随机数&#xff0c;最后在窗口显示排序后的数字&#xff1a; mainwindow.h文件…...

【Java】泛型 之 使用泛型

使用ArrayList时&#xff0c;如果不定义泛型类型时&#xff0c;泛型类型实际上就是 Object&#xff1a; // 编译器警告: List list new ArrayList(); list.add("Hello"); list.add("World"); String first (String) list.get(0); String second (Strin…...

消费者NPS调查,帮您了解客户满意度!

随着市场竞争的日益激烈&#xff0c;了解消费者需求和对企业品牌的认知程度&#xff0c;对于企业的持续发展至关重要。您的客户对您的产品或服务有多满意?您是否想提升客户忠诚度&#xff0c;从而增加业务的持续增长?群狼调研(长沙产品包装测试)为您提供全新的消费者NPS调查服…...

Webpack监视文件修改,自动重新打包文件

方法一&#xff1a;使用watch监视文件变化 在终端中输入以下指令&#xff1a; npx webpack --watch 我们使用这种方法监听文件变化时只会监听我们计算机本地的文件变化&#xff0c;在开发场景中我们的项目是要部署到服务器中的&#xff0c;因此这种方式并不推荐。 方法二&…...

list容器排序案例

案例描述:将Perspn自定义数据类型进行排序&#xff0c;Person中属性有姓名、年龄、身高 排序规则:按照年龄进行升序&#xff0c;如果年龄相同按照身高进行降序 代码示例 #include <iostream> #include <string.h> #include <iterator> #include <vector…...

PHP使用Analysis中英文分词

1、下载Analysis&#xff0c;创建test.php测试 2、引入Analysis实现中文分词 <?php include "./Analysis/Analysis.php";$annew \WordAnalysis\Analysis(); $content"机器学习是一门重要的技术&#xff0c;可以用于数据分析和模式识别。"; //10分词数…...

视频汇聚/视频云存储/视频监控管理平台EasyCVR录像存储功能如何优化?具体步骤是什么?

视频云存储/安防监控EasyCVR视频汇聚平台基于云边端智能协同&#xff0c;支持海量视频的轻量化接入与汇聚、转码与处理、全网智能分发、视频集中存储等。视频监控系统EasyCVR拓展性强&#xff0c;视频能力丰富&#xff0c;具体可实现视频监控直播、视频轮播、视频录像、云存储、…...

Web服务(Web Service)

简介 Web服务&#xff08;Web Service&#xff09;是一种Web应用开发技术&#xff0c;用XML描述、发布、发现Web服务。它可以跨平台、进行分布式部署。 Web服务包含了一套标准&#xff0c;例如SOAP、WSDL、UDDI&#xff0c;定义了应用程序如何在Web上实现互操作。 Web服务的服…...

Java第4章 类的继承

目录 内容说明 章节内容 一、继承的概念 二、继承的使用 extends关键字...

Linux网络和安全:配置、远程访问与防御指南

文章目录 Linux 网络和安全引言网络配置IP地址配置配置网络接口防火墙设置安全性加强 Linux网络配置及端口管理网络配置命令端口管理 防火墙和安全性设置防火墙管理工具安全性设置 Linux远程访问技术&#xff1a;SSH和VPNSSHVPN Linux软件和服务网络工具文件传输VPN技术安全审计…...

如何搭建Linux环境

W...Y的主页 &#x1f60a; 代码仓库分享 &#x1f495; 当我们想要搭建一个Linux系统&#xff0c;我们应该怎么使用呢&#xff1f; 今天我就带领大家搭建Linux系统&#xff01;&#xff01;&#xff01; 目录 Linux环境安装 双系统&#xff08;不推荐&#xff09; poww…...

【解决方案】edge浏览器批量添加到集锦功能消失的解决方案

edge的集锦功能很好用&#xff0c;右键标签页会出现如下选项&#xff1a; 但在某次edge更新后&#xff0c;右键标签页不再出现该选项&#xff1a; 这里可以参考为什么我的Edge浏览器右键标签页没有“将所有标签页添加到集锦”功能&#xff1f; - Microsoft Community 一文提出…...

JS操作字符串方法学习系列(1)-每天学习10个方法

目录 **字符串连接 (Concatenation)**:**字符串长度 (Length)**:**字符串查找 (Search)**:**字符串替换 (Replace)**:**字符串分割 (Split)**:**字符串大小写转换 (Case Conversion)**:**字符串切片 (Slice)**:**字符串删除空白 (Trim)**:**字符串检查开头和结尾 (Starts/EndsW…...

iterator和generator

iterator和generator iterator es6: let/const ...展开 迭代器 是一种机制&#xff0c;比如在控制台输出Iterator是没有这个类的&#xff0c;为不同的数据结构提供迭代循环的机制。 迭代器对象&#xff1a;具备next方法&#xff0c;next能够对你指定的数据进行迭代循环&#x…...

ipv6笔记及总结

1、路由器请求消息Router Solicitation和路由器通告Router Advertisement消息主要用于无状态地址的情况下&#xff0c;有状态的情况使用的是dhcpv6 server分配&#xff08;例如&#xff1a;IPv6地址以及其他信息&#xff08;DNS、域名等&#xff09;&#xff09;。 2、关于IPv…...

64位Ubuntu20.04.5 LTS系统安装32位运行库

背景&#xff1a; 在ubutu&#xff08;版本为20.04.5 LTS&#xff09;中运行./arm-none-linux-gnueabi-gcc -v 后提示“no such device”。 经多方查证&#xff0c;是ubutu的版本是64位的&#xff0c;而需要运行的编译工具链是32位的&#xff0c;因此会不兼容。 解决方法就是在…...

关于vue.config.js

关于vue.config.js 简述 vue.config.js是一个可选的配置文件&#xff0c;如果项目的根目录中存在这个文件&#xff0c;那么它就会被vue/cli-service自动加载。你也可以使用package.json中的vue字段&#xff0c;但是注意这种写法需要你严格遵守JSON的格式来写。 这个文件应该…...

Jupyter NoteBook 中使用 cv2.imshow 显示图片

Jupyter NoteBook 中使用 cv2.imshow 显示图片 有两种办法: 用 cv2.imshow时加入cv2.destroyAllWindows() 用 plt.imshow() 代替 cv2.imshowhttps://blog.csdn.net/kuweicai/article/details/103359299...

gpt扣款失败,openai扣款失败无法使用-如何解决gpt扣款失败的问题?

gpt扣款失败&#xff0c;openai扣款失败无法使用。毕竟你花了钱却无法使用你所期待的服务&#xff0c;这种情况确实令人不快。但是&#xff0c; 为什么gpt扣款失败&#xff1f; 可能是由于支付问题导致的扣款失败。这包括信用卡额度不足、支付信息错误等等。如果你的支付信息…...

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度​

一、引言&#xff1a;多云环境的技术复杂性本质​​ 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时&#xff0c;​​基础设施的技术债呈现指数级积累​​。网络连接、身份认证、成本管理这三大核心挑战相互嵌套&#xff1a;跨云网络构建数据…...

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻

在如今就业市场竞争日益激烈的背景下&#xff0c;越来越多的求职者将目光投向了日本及中日双语岗位。但是&#xff0c;一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧&#xff1f;面对生疏的日语交流环境&#xff0c;即便提前恶补了…...

服务器硬防的应用场景都有哪些?

服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式&#xff0c;避免服务器受到各种恶意攻击和网络威胁&#xff0c;那么&#xff0c;服务器硬防通常都会应用在哪些场景当中呢&#xff1f; 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...

大学生职业发展与就业创业指导教学评价

这里是引用 作为软工2203/2204班的学生&#xff0c;我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要&#xff0c;而您认真负责的教学态度&#xff0c;让课程的每一部分都充满了实用价值。 尤其让我…...

CSS设置元素的宽度根据其内容自动调整

width: fit-content 是 CSS 中的一个属性值&#xff0c;用于设置元素的宽度根据其内容自动调整&#xff0c;确保宽度刚好容纳内容而不会超出。 效果对比 默认情况&#xff08;width: auto&#xff09;&#xff1a; 块级元素&#xff08;如 <div>&#xff09;会占满父容器…...

MySQL JOIN 表过多的优化思路

当 MySQL 查询涉及大量表 JOIN 时&#xff0c;性能会显著下降。以下是优化思路和简易实现方法&#xff1a; 一、核心优化思路 减少 JOIN 数量 数据冗余&#xff1a;添加必要的冗余字段&#xff08;如订单表直接存储用户名&#xff09;合并表&#xff1a;将频繁关联的小表合并成…...

mac 安装homebrew (nvm 及git)

mac 安装nvm 及git 万恶之源 mac 安装这些东西离不开Xcode。及homebrew 一、先说安装git步骤 通用&#xff1a; 方法一&#xff1a;使用 Homebrew 安装 Git&#xff08;推荐&#xff09; 步骤如下&#xff1a;打开终端&#xff08;Terminal.app&#xff09; 1.安装 Homebrew…...

CSS3相关知识点

CSS3相关知识点 CSS3私有前缀私有前缀私有前缀存在的意义常见浏览器的私有前缀 CSS3基本语法CSS3 新增长度单位CSS3 新增颜色设置方式CSS3 新增选择器CSS3 新增盒模型相关属性box-sizing 怪异盒模型resize调整盒子大小box-shadow 盒子阴影opacity 不透明度 CSS3 新增背景属性ba…...

字符串哈希+KMP

P10468 兔子与兔子 #include<bits/stdc.h> using namespace std; typedef unsigned long long ull; const int N 1000010; ull a[N], pw[N]; int n; ull gethash(int l, int r){return a[r] - a[l - 1] * pw[r - l 1]; } signed main(){ios::sync_with_stdio(false), …...