java数据结构基础题型及解法

大家好，我是讯享网，很高兴认识大家。

付费加入星球之后可以阅读全面内容（备注微信昵称） 25届动态更新题单（预计5月份底6月初更新完成，新增30天打卡，公司高频考点总结）https://t.zsxq.com/ic7Ci 24届题单已经更新完（战绩：1w人传阅、付费用户500+） https://t.zsxq.com/ic7Ci ![](images/image-4.png) # 绪论 复杂度 在介绍具体的数据结构与算法之前，我们需要学习有关复杂度的概念，因为一切不考虑时空间复杂度的算法都是扯淡！！！对于校招生来说，需要熟练掌握时空间复杂度，才能够在笔试中的有限时间内写出满足题目条件，可以正确运行并不超时的代码；对于自己在面试过程中写的代码，也需要能快速地分析出代码的时空间复杂度，才可以应对面试官的一些问题（例如：这道题你提供的代码时间复杂度是多少？有没有更快的做法...） 复杂度是一个关于输入数据量$n$的函数，下面将分别从时间和空间两个维度对复杂度进行详细介绍。 时间复杂度 假设某一个程序的时间复杂度为$O(n)$，则说明该程序的执行效率与输入的数据量 线性相关，假设某一个程序的时间复杂度为$O(n^2)$，则说明该程序的执行效率与输入的数据量 的平方线性相关。 时间复杂度与程序的执行效率成反比，例如当$n=100$时，时间复杂度为$O(n)$的算法比时间复杂度为$O(n^2)$的算法执行效率约快1000倍左右 时间复杂度的计算有以下几个计算规则 * 复杂度与具体的常数系数无关，例如$O(2n)$和$O(n)$表示的是相同程度的复杂度 * 一段程序的时间复杂度，只看最高项，例如$O(n^2+2 imes n+3 imes log(n))$，这段程序的时间复杂度应该取最高项，为$O(n^2)$ 为什么时间复杂度很重要？ 因为所有的笔试题，题目都会给一个时间限制，这个时间限制的意思是，你写的代码在运行后台提供的测试样例中，需要在规定的时间内运行完，一般给的时间为1s，有的会卡500ms。 一般情况下，计算机1s可以执行$10^7sim 10^8$次操作，因此我们需要把我们程序执行的最大次数控制在这个区间内，一般控制在$3 imes 10^7$较为安全。例如题目给定数据范围是$nle 10^5$，我们就不能设计出$O(n^2)$的算法，因为一定会被后台的一些测试样例卡住，然后提交代码只会显示部分通过（遇到严格的测试样例，只有10%左右的通过率），如果我们设计出$O(n)$或者$O(nlogn)$的算法，那就可以100%通过这道题的所有测试样例。 $O(nlogn)$的最坏情况是：$O(10^5 imes log(10^5))$，其中$log(10^5)=5log(10)approx 6 imes 3=18$ ($log(8)=3,log(10)=3.32$) 因此$O(10^5 imes log(10^5))approx O(10^5 imes 15)=O(1.5 imes 10^6)$，因此可以在1s中执行完。 根据时间复杂度反推数据结构与算法 下面的 就是题目给定的数据规模，建议大家对这个模块，一边刷题一边回过头来反复理解，会加深自己的印象 > * $nle 20$，这一类题目的数据范围较小，可以直接使用DFS算法，来枚举所有的情况，例如DFS专题中的二进制枚举，对应的复杂度为$O(2^n)$或者$O(n imes 2^n$，在当前给定数据范围内，$O(n imes 2^n)$的最坏执行次数为$O(20 imes 2^{20})approx O(20 imes 10^6)=O(2 imes 10^7)$，其中$2^{10}=1024approx 10^3$ > > * $nle 10$，这一类题目可以使用$O(n^3)$以内复杂度的算法求解，这一类题型可能会涉及到二维前缀和、动态规划等算法。 > > * $nle 10^5$，这一类题目可以使用$O(n)$或者$O(nlogn)$复杂度的算法求解，这一类题型可能涉及到堆（优先队列）、排序、动态规划、树状数组、堆优化版dijkstra、二分查找、二分答案、质数筛等。 > > * $nle 10^5$，这一类题目可以使用$O(sqrt{n})$或者$O(logn)$复杂度的算法求解，这一类题型可能涉及到判断质数、因子个数计算、二分答案、快速幂、最大公约数等。 > > * $nle 10^{1000}$，这一类题目可以使用$O(logn)$或者$O((logn)^2)$复杂度的算法求解，这一类题型很大概率是数位DP。 空间复杂度 空间复杂度的概念和时间复杂度很类似，时间复杂度是反映程序执行的效率，空间复杂度是反映程序执行所需存储空间的大小，例如，输入数据量为 ，你申请了一个长度为 的一维数组，那么对应的空间复杂度为$O(n)$，如果申请的是二维数组，那么对应的空间复杂度为$O(n^)$ 一般题目给定的空间内存要求为64MB，$64MB=2^6 imes 1MB=2^6 imes 2^{10} B=2^6 imes 2^{10} imes 2^{10} Byte=2^{26}Byte$ 如果申请的是int型的数组，每个元素占用4个字节（$Byt$），因此可以申请$2^{24}$长度的空间，也就是近似$10^7$左右的范围。 一般对于给定的题目来说，申请一维数组的长度尽量不要超过$5 imes 10^6$，申请二维数组的长度尽量不要超过$3 imes 10^3$，大家当结论记就行。 ACM模式及相关模板 刷习惯Leetcode的同学，刚开始做笔试题可能会很不适应，因为Leetcode是核心代码模式，只需要写具体的处理逻辑，不需要对题目的输入格式来处理输入数据，并对答案进行输出，下面提供几个ACM模式的例子，供大家参考和练习。 单组输入 笔试题目的输入类型以这种最为常见，一般最常见的就是第一行给定一个整数 ，表示数组大小，第二行给定 个整数，每个整数用空格隔开，表示数组中的 个数字，也有一些题目故意不给 的大小，直接给 个整数，详见下面的样例。 示例1 第一行给定一个整数 ，表示数组大小，第二行给定 个整数，每个整数用空格隔开，表示数组中的 个数字，请你返回数组中的元素之和。 输入样例 ```plain&#x20;text 5 1 2 3 4 5 ``` 输出样例 C++ ```c++ #include<bits/stdc++.h> using namespace std; const int N=1E5+10; int w[N],n; int main(){ cin>>n; //读入数组大小 for(int i=0;i<n;i++){ cin>>w[i]; //读取n个整数 } long long sum=0; for(int i=0;i<n;i++){ sum+=w[i]; } cout<<sum<<endl; // 输出元素和 return 0; } ``` Java ```java import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int N = ; // 假设数组大小最多为 int[] w = new int[N]; int n = scanner.nextInt(); // 读取数组大小 for (int i = 0; i < n; i++) { w[i] = scanner.nextInt(); // 读取n个整数 } long sum = 0; for (int i = 0; i < n; i++) { sum += w[i]; } System.out.println(sum); // 输出元素和 } } ``` Python ```python # 从用户输入读取一个整数，表示列表中元素的个数 n = int(input()) # 从用户输入读取一个由空格分隔的整数列表 w = list(map(int, input().split())) # 初始化一个变量来存储列表元素的总和 sum_result = 0 # 遍历列表中的每个元素 for x in w: # 将当前元素添加到总和中 sum_result += x # 打印最终的总和结果 print(sum_result) ``` 示例2 给定一个$n*m$的矩形，矩形中的元素不是1就是0，每个1可以和上下左右四个方向的1构成一整个连通块，求这个矩形中含有的连通块数量 其实就是LeetCode原题，改成了ACM模式：[LeetCode 200. 岛屿数量](https://leetcode.cn/problems/number-of-islands/) 输入描述 第一行输入两个整数$n,$用空格隔开 接下来 行，每行输入 个整数，用`,`隔开 输入样例 ```plain&#x20;text 3 3 1,1,1 0,0,1 1,0,1 ``` C++选手可以使用`scanf()`来处理不同的分隔符 ```c++ scanf("%d,"&w[i]) //以,为分隔符 scanf("%d?",&w[i]); //以?为分隔符 ``` Java选手可以使用正则表达式来把`,`作为分隔符的一种 Python选手可以使用`spilt()`的一些特性来处理 C++ ```c++ #include<bits/stdc++.h> using namespace std; const int N=1010; int g[N][N]; int n,m; int main(){ cin>>n>>m; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ scanf("%d,",&g[i][j]); cout<<g[i][j]<<" "; } puts(""); } return 0; } ``` Java ```java import java.util.Scanner; public class Main { public static void main(String[] args) { // 创建 Scanner 对象，用于从标准输入读取数据，设置分隔符为逗号或空白字符 Scanner scanner = new Scanner(System.in).useDelimiter(",|\s+"); // 定义矩阵的最大大小 int N = 1010; // 创建二维数组，用于存储矩阵数据，数组大小为 N 行 N 列 int[][] g = new int[N][N]; // 声明变量 n 和 m，用于表示矩阵的行数和列数 int n, m; // 从输入中读取一个整数，表示矩阵的行数，并将其赋值给变量 n n = scanner.nextInt(); // 从输入中读取一个整数，表示矩阵的列数，并将其赋值给变量 m m = scanner.nextInt(); // 外层循环迭代矩阵的每一行，i 表示当前行的索引 for (int i = 0; i < n; i++) { // 内层循环迭代矩阵的每一列，j 表示当前列的索引 for (int j = 0; j < m; j++) { // 从输入中读取一个整数，表示矩阵中当前位置的值，并将其赋值给二维数组 g 的对应位置 g[i][j] = scanner.nextInt(); // 打印矩阵中当前位置的值，以及一个空格 System.out.print(g[i][j] + " "); } // 在内层循环结束后换行，以打印下一行的值 System.out.println(); } // 关闭 Scanner 对象 scanner.close(); } } ``` Python ```python n, m = map(int, input().split()) g = [[0] * n for _ in range(m)] for i in range(n): row = list(map(int, input().split(','))) for j in range(m): g[i][j] = row[j] print(g[i][j], end=" ") print() ``` 示例3 给定一行数字，每个数字用空格隔开，请你将这些数字排序后并输出排序后的结果 输入样例 ```plain&#x20;text 8 5 4 2 7 ``` 输出样例 ```plain&#x20;text 2 4 5 7 8 ``` C++ ```c++ #include<bits/stdc++.h> using namespace std; int main(){ vector<int>w; int x; while(cin>>x){ //读取一行的数据 w.push_back(x); } sort(w.begin(),w.end()); for(int &x:w){ //输出排序后的结果 cout<<x<<" "; } } ``` Java ```java import java.util.ArrayList; import java.util.Collections; import java.util.Scanner; public class Main { public static void main(String[] args) { // 创建 ArrayList 对象，用于存储整数数据 ArrayList<Integer> w = new ArrayList<>(); // 创建 Scanner 对象，用于从标准输入读取数据 Scanner scanner = new Scanner(System.in); // 循环读取一行的数据，直到输入结束 while (scanner.hasNextInt()) { int x = scanner.nextInt(); // 将读取的整数添加到 ArrayList 中 w.add(x); } // 使用 Collections 类中的 sort 方法对 ArrayList 进行排序 Collections.sort(w); // 遍历排序后的 ArrayList，输出结果 for (int x : w) { System.out.print(x + " "); } // 关闭 Scanner 对象 scanner.close(); } } ``` Python ```python w=list(map(int,input().split())) #python选手福音 w.sort() print(*w) ``` 多组输入 其实就是题目的输入样例包含多组输入，每一组输入有对应的规则，然后最后需要返回每一组输入的输出结果 示例 第一行给定一个整数 ，表示输入样例的组数，接下来$T*2$行，第一行给定一个整数 ，表示数组大小，第二行给定 个整数，每个整数用空格隔开，表示数组中的 个数字，请你返回每一组的数组中的元素之和。 输入样例 ```plain&#x20;text 3 4 3 2 1 4 5 1 4 5 6 7 3 2 3 1 ``` 输出样例 ```plain&#x20;text 10 23 6 ``` 这类问题其实相比与上面两种，反而是最简单的，因为只需要在外面多套一层循环即可，其他的逻辑基本上不需要修改 建议可以写一个函数处理每组数据，然后就是把当前的函数执行 次， 为输入数据的组数 多组数据的一个坑点，就是在某些情况，需要初始化一些数组变量，否则在单组测试样例没问题，多组测试样例就会出错。 C++ ```c++ #include<bits/stdc++.h> using namespace std; const int N=1E5+10; int n,w[N],T; void solve(){ //处理每一组数据的函数 cin>>n; for(int i=0;i<n;i++){ cin>>w[i]; } long long sum=0; for(int i=0;i<n;i++){ sum+=w[i]; } cout<<sum<<endl; } int main(){ cin>>T; //T组测试数据 while(T--){ solve(); } } ``` Java ```java import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); // 创建一个Scanner对象来接收用户输入 int T = scanner.nextInt(); // 从控制台读取一个整数T，表示多组测试数据 for (int i = 0; i < T; i++) { // 循环T次，调用solve方法处理每组测试数据 solve(scanner); } } static void solve(Scanner scanner) { int n = scanner.nextInt(); // 从控制台读取一个整数n int sum = 0; // 初始化一个变量sum来存储列表元素的总和 for (int i = 0; i < n; i++) { // 循环n次，读取n个整数并计算它们的总和 int x = scanner.nextInt(); // 从控制台读取一个整数x sum += x; // 将x添加到总和中 } System.out.println(sum); // 打印最终的总和结果 } } ``` Python ```python def solve(): n=int(input()) w=list(map(int,input().split())) sum=0 for x in w: sum+=x print(sum) T=int(input()) #多组测试数据 for _ in range(T): solve() ``` 笔试介绍&相关技巧 * 笔试介绍：笔试一般时间为90-120分钟，除了美团是五道编程题，字节、携程、微众银行等个别公司是四道编程题，其他大部分公司（例如阿里系（其中包含阿里淘天、蚂蚁、银泰百货、阿里大文娱、阿里国际等等）、华为、米哈游、ak_coding书等公司）都是三道编程题，当然也有一些公司是两道编程题，我们要对整个笔试的难度有所把握，尽可能达到编程总成绩的60%及以上，这样进面试的机会会大一些 $编程总成绩=sum 每道题的通过率 imes 每道题的总分值$ 特殊情况：例如华为三道题的分值分别为100、200、300，那么你只需要保证第二题在75%以上的通过率，即使不做第一题、第三题也可以通过笔试，但是像米哈游这种要求很高的公司，基本上需要笔试成绩接近满分（AK）才有机会进入面试。 笔试中每道题的对应难度 五道编程题：前2题easy，第三题easy~medium，第四题medium~hard，第五题hard 四道编程题：前两题easy，第三题medium~hard，第四题hard 三道编程题：第一题easy，第二题medium，第三题hard * 笔试相关技巧&细节问题 > 1.做笔试题切记不要死磕，一道题如果20分钟甚至30分钟都没有思路或者有思路实现的时候有问题，立刻去往后看看后面的题目是否有自己可以写的，一旦死磕一道题，时间很容易白白浪费，错失良机。 > > 2.笔试的题目，难度并不一定是严格递增的，有以下两种情况 > > 情况1：这套题的实际难度并不是T1<T2<T3，有可能是T1>T3>T2或者T2>T3>T1 > > 情况2：每个人擅长的算法和数据结构不一样，因此笔试题的难度只能说作为一个整体的难度来定义，可能有的hard题对于一些做过这种套路性题的同学来说堪比easy，但有的medium题目对于一些从来没做过这类题型的同学就是hard级别，因此一定要至少每道题花个3-5分钟浏览一下题意，然后大致有一个判断来决定是做这道题还是继续回去磕前面的题目。 > > 2.不会做的题要会骗分 > > 例如，数据范围$nle 10^5$，很明显只能使用$O(n)$或者$O(nlogn)$的算法来求解，但是如果一时想不到优化策略，可以先写一个$O(n^2)$的算法，去拿部分通过率的分数，有时候遇到出题人样例出的很弱，甚至可以通过50%以上的样例，但是大部分情况下，一般通过率都是只有不到20%，但是有总比没有强 > > 还有一些情况，答案要求你输出一个方案数，你就可以输出一个跟输入数据规模 相关的一个数字，例如$n^2,n^3,n imes (n-1),frac{n}{2}$等等，碰碰运气，有时候会有意外收获 > > 3.对于一些有自信能100%通过的题，但是只有很低的通过率，要学会从以下几点去找原因 > > 数据范围，对于C++和Java选手，题目数据范围给的是$2 imes 10^5$，你的数组是否开小了 > > 数值范围，对于C++和Java选手，题目数值范围给的是$-10^9le valle 10^9$，你的答案很多时候就不能用`int`型变量来作为输出了，要使用`long long`或者`long`输出，这个地方初学者经常容易犯错，必须要吃过一两次亏才长记性hh > > 对于一些图论问题，题目只要没有明确说是有向图，就一定要按照无向图的模版来构建图，初学者很容易出错的一点是，题目给定了根节点的编号（一般为1），但是他自己构建的时候按照有向图来构建，导致可能样例通过了，但是通过率极低，就是因为需要构建无向边（因为样例给定的两个点`a`和`b`可能恰好和图中的方向一致） 题目难度说明 > 题单中的每道题，都会标记一个难度系数 ， 的范围为$1le k le 9$ > > $1le k le 3$ 对应的是模板题或者是简单模拟题，对应笔试中的第一题签到题的难度 > > $4le k le 6$ 对应的是中等难度的题目，一般出现在笔试题的中间位置，例如美团的第三题、第四题，阿里系的第二题，有的题目的题面比较复杂，需要有一定抽象问题的能力（把问题转化为某一个算法问题求解，比如转化为区间加法问题，然后使用差分数组求解，或者转化为图的顺序访问问题，使用拓扑排序求解），也有的题目需要使用到一些小技巧，如二分答案，前后缀分解等 > > $7le k le 9$ 对应的是困难难度的题目，一般是笔试题的压轴题，可能会涉及一些数学题或者思维题（比如数学问题中的组合数学，贡献法计数，正难则反/逆向考虑这种思想），又或者一些比较笔试中考的很难的算法，比如树形DP、树状数组、逆元等。 > > 注意：本难度只是一个大致的说明，并没有绝对的标准，有的6分题可能有些同学做起来比8分题还难，有些7分题可能对于一些同学来说并没有那么难，每个同学擅长的考点和题型是不完全相同的。 # 大厂笔试Ak_coding之王 大家好，我是ak_coding，是《大厂笔试通关手册》的作者，本手册是我从一个连数据结构是什么都不了解的“学渣”到最终能够实现秋招笔试全通关，最终拿下多个大厂offer的“收割机”过程的经验和技巧总结；在秋招后我又花了几个月的时间进行了重新的沉淀思考、提炼总结，最终形成了本手册。 在此之前几个月，我跟内推鸭的朋友们一起合作，招募了几百名内测用户，他们在结合本手册学习的基础上算法能力得到了极大提高，在正在进行的春招和实习的笔试中通过率有了极大提升。 现在，我们也能够终于放心的把本手册正式推出，分享给更多的同学，让算法笔试和面试不再成为大家求职路上的拦路虎。 一、我是谁？ ak_coding，本硕非科班，研究生之前没有接触过算法，甚至连一些基本的数据结构都不知道，在经历了痛苦的摸索学习和大量的实战练习后，总结了12万字的学习方法手册，对算法笔试套路和常见题型非常熟悉，秋招笔试全通关，最终拿下了多家大厂的offer，指导过数百名求职大厂同学的算法刷题，获得了明显提升。 内推鸭，大学生求职平台，为校招/实习的大学生提供求职信息和内推平台，并联合了众多KOL与行业专家为求职者提供简历、笔试、面试等全方位的求职指导，帮助10w+求职者顺利拿到offer。 二、本手册有什么特别之处？ 与市面上常见的算法书籍不同，本手册是真正的大厂笔面试实战经验总结，针对性特别强，而且是作者从算法小白到高手的历程总结，对于普通同学怎么提高算法能力有很强的效果加成。 本手册的题单涉及的知识点更加全面，丰富，针对笔试对知识点进行分类和总结，而且题目50%以上都是ACM模式的题，帮助大家更好地适应笔试题目；且对常见算法总结了Java，Python，C++的算法模版，方便大家更好地应对笔试； 题单主要是根据笔试常考的考点，做详细的一个知识点划分，比如动态规划会分成背包问题，字符串 DP，线性 DP，状态机DP，树形 DP，数位 DP 等多个部分，每一个部分会有入门的题目和相应模板，比如常考的前缀和，差分，二分答案，树形DP等，都有对应的模板题和模板，供大家参考学习。每个知识点都包含5~15道算法题，其中有一半甚至70%的题目都是ACM模式的算法题，整个题单的题目数量有300道，包含95%以上的笔试考点，足够让大家应付字节跳动、美团、网易、米哈游等互联网公司的笔试和面试算法题目的考验。 三、知识星球都有什么？ 在本手册的基础上，为了更好的帮助大家学习，以及加强互动交流，更好的提升大家的算法能力，我们特别创建了知识星球，在知识星球里面可以获得： * 大厂笔试/面试算法通关手册； * 算法问题交流和答疑，手册作者和特邀KOL会跟大家经常交流； * 最新大厂笔试交流，考后第一时间复盘提升自己； * 丰富的刷题打卡和题解分享活动，在好的算法学习氛围中，事半功倍。 四、如何订阅本手册&加入知识星球？ 本手册面向以下人群，可放心订阅： * 面临校招或者实习求职的大学生； * 想要提升算法能力的大学生； * 想要保持或者继续提升算法能力的职场人。 因为算法学习提升需要伴随着大量的刷题，建议大家要提早准备，或者把算法学习和刷题当成日常，不要临时抱佛脚，快要笔试或者面试了再去刷题、再去学习肯定是来不及的。 目前价格是119，前100人给大家19优惠券，知识星球会陆续涨价到169，推荐25届及时加入，这里面将会及时发布关于25届秋招信息 ![](<images/星球优惠券 (5).png>) # 全面题单总结构（学完笔试ak 60-80%） 第一章：基础算法与数据结构 包含内容：双指针、二分查找、哈希表、前缀和、差分 ![]() 第二章：高级数据结构 包含内容：单调栈、单调队列、堆（优先队列）、并查集、树状数组 ![]() 第三章：搜索与图论 包含内容：DFS、BFS、拓扑排序、Dijkstra、最小生成树 ![]() 第四章：动态规划 包含内容：背包DP、线性DP、序列DP、记忆化搜索、状态机DP、树形DP、期望DP、数位DP ![]() 第五章：数论 筛质数、因子个数、最大公约数、最小公倍数、位运算、乘法原理、快速幂、组合数学、逆元 第六章：贪心 中位数贪心、堆贪心、反悔贪心、思维贪心 ![]() # 2024考点汇总 美团2024高频考点 | 公司名称 | 一级考点分析 | 二级考点分析 | 出现频次 | 题目名称 | | ---- | ------ | --------------- | ---- | ---------------------------------------- | | 美团 | 模拟 | 字符串模拟 | 2 | 2024.3.9-第一题、2024.4.6-第一题 | | 美团 | 模拟 | 简单模拟 | 2 | 2024.3.16-第一题、2024.3.30-第一题、 | | 美团 | 模拟 | 数组模拟 | 2 | 2024.3.23-第一题、2024.4.13-第一题 | | 美团 | 模拟 | 分类讨论 | 3 | 2024.3.16-第二题、2024.3.30-第三题、2024.4.6-第二题 | | 美团 | 模拟 | 排序 | 1 | 2024.3.30-第二题、 | | 美团 | 贪心 | 排序 | 2 | 2024.3.9-第二题、2024.4.13-第二题 | | 美团 | 贪心 | 思维 | 1 | 2024.3.23-第二题、 | | 美团 | 贪心 | 哈希表 | 1 | 2024.3.23-第三题、 | | 美团 | 前缀和 | 一维前缀和 | 1 | 2024.4.6-第三题、 | | 美团 | 前缀和 | 二维前缀和 | 1 | 2024.3.9-第三题、 | | 美团 | 双指针 | 不定长滑动窗口 | 1 | 2024.3.9-第四题、 | | 美团 | 数据结构 | 并查集 | 1 | 2024.3.9-第五题、 | | 美团 | 数据结构 | 树状数组 | 2 | 2024.3.16-第四题、2024.3.16-第五题、 | | 美团 | 数论 | 快速幂 | 1 | 2024.3.16-第三题、 | | 美团 | 数论 | 组合数学、乘法逆元 | 1 | 2024.3.30-第四题、 | | 美团 | 数论 | 因子个数、一维前缀和、二分查找 | 1 | 2024.4.13-第一题 | | 美团 | 图论 | LCA、乘法逆元 | 1 | 2024.3.23-第五题、 | | 美团 | 图论 | Tarjan算法 | 1 | 2024.3.30-第五题、 | | 美团 | 动态规划 | 线性DP | 1 | 2024.4.6-第四题、 | | 美团 | 动态规划 | 线性DP、乘法逆元 | 1 | 2024.4.6-第五题、 | | 美团 | 动态规划 | 树形DP | 1 | 2024.4.13-第三题、 | | 美团 | 动态规划 | 序列DP | 1 | 2024.4.13第五题 | 阿里2024高频考点 | 公司名称 | 一级考点分析 | 二级考点分析 | 出现频次 | | ---- | ------ | ------- | ---- | | 阿里 | 模拟 | 分类讨论 | 3 | | 阿里 | 模拟 | 简单模拟 | 3 | | 阿里 | 数据结构 | 堆 | 2 | | 阿里 | 数据结构 | 哈希表 | 2 | | 阿里 | 数据结构 | 树状数组 | 1 | | 阿里 | 数据结构 | 并查集 | 2 | | 阿里 | 前缀和 | 一维前缀和 | 2 | | 阿里 | 二分 | 二分查找 | 1 | | 阿里 | 二分 | 二分答案 | 2 | | 阿里 | 搜索 | DFS | 1 | | 阿里 | 动态规划 | 线性DP | 4 | | 阿里 | 动态规划 | 背包问题 | 2 | | 阿里 | 动态规划 | 序列DP | 3 | | 阿里 | 动态规划 | 记忆化搜索 | 1 | | 阿里 | 数论 | 贡献法计数 | 3 | | 阿里 | 数论 | 质数 | 2 | | 阿里 | 数论 | 质因数分解 | 1 | | 阿里 | 数论 | 快速幂 | 2 | | 阿里 | 数论 | 组合数学 | 1 | | 阿里 | 数论 | 乘法逆元 | 1 | | 阿里 | 数论 | 最大公约数 | 2 | | 阿里 | 数论 | 容斥定理 | 1 | | 阿里 | 贪心 | 排序 | 2 | | 阿里 | 贪心 | 枚举、分类讨论 | 2 | | 阿里 | 贪心 | 位运算 | 1 | | 阿里 | 贪心 | 反悔贪心 | 1 | 字节跳动2024高频考点 | 一级考点分析 | 二级考点分析 | 出现频次 | | ------ | ------- | ---- | | 模拟 | 简单模拟 | 3 | | 双指针 | 不定长滑动窗口 | 1 | | 前缀和 | 一维前缀和 | 1 | | 前缀和 | 二维前缀和 | 1 | | 数据结构 | 单调栈 | 1 | | 数据结构 | 哈希表 | 2 | | 数据结构 | 并查集 | 1 | | 搜索 | 树形DFS | 2 | | 动态规划 | 线性DP | 2 | | 动态规划 | 期望DP | 1 | | 动态规划 | 数位DP | 1 | | 动态规划 | 01背包 | 1 | | 贪心 | 排序 | 1 | | 贪心 | 正难则反 | 1 | | 贪心 | 中位数贪心 | 1 | | 数论 | 贡献法计数 | 2 | | 数论 | 组合数学 | 1 | | 数论 | 快速幂 | 1 | | 数论 | 容斥定理 | 1 | 更多2024高频考点参考全面版 ![](images/image.png) # 第一章 基础数据结构与算法 双指针 算法讲解 基础算法之一，也是笔试中比较常考的一个算法，双指针题型以及变型有很多，这里面主要列举两大类 一类是在两个数组中使用两个指针分别指向这两个数组，这一类问题中，最经典的就是判断子序列的问题 另一类则是在一个数组中使用两个指针指向这一个数组，这类问题又称为同向双指针问题，也称为滑动窗口问题，这类问题的又可以细分为两类，第一类比较简单，可以称为定长滑动窗口，就是窗口大小是固定的，例如，给定窗口长度为 ，需要计算在这个长度为 的窗口中的最大值/最小值/最大和等。 第二类则是笔试和面试都考察比较多的问题，也就是不定长滑动窗口，这一类题目一般是要求满足题目某个条件下的最大值/最小值/最大长度/最小长度/区间最大和/区间最小和/方案数。这一类题目，大家如果学习完动态规划这一章节之后，会发现他其实是有一种动态规划的思想在，例如给定`l`和`r`两个双指针，很多问题其实就变为以`r`结尾的最大值/最小值，这类问题是需要满足单调性的：当`[l,r]`区间不满足条件时，`l`指针需要左移，直到`[l,r]`区间满足条件为止，且当`l=r`时，都可以满足条件，很多时候，如果数组的数值可以取负数，是不能使用双指针来求最优解的，就是因为不满足单调性，这种题目其实比较难的是一种抽象问题的能力，有的题目需要把问题做一个转化，首先需要判断是否满足单调性，如果满足，就需要把问题转化为一个可以使用双指针去解决的一个滑动窗口问题。 算法模版 这里给出的算法模版仅针对不定长滑动窗口问题，这一类的问题可以抽象为四大类 第一类：最长上升/下降子数组 第二类：求最大值/最大长度 第三类：求最小值/最小长度 第四类：求子数组个数 [最长上升子数组](http://121.196.235.151/p/P1003) 上述例子中，最长上升子数组的长度为3，对应的结果为$[2,4],6$ 下面讲解如何使用双指针算法，来对这个问题进行求解，首先定义两个指针$l,r$，并指向数组的最左边的元素位置，将最长上升子数组的长度$an$初始化为0 * 第一步：固定$l$指针，移动$r$指针，直到走到以$l$开头的最长上升子数组的最后一个位置，对于本样例，其实就是走到3（因为下一个位置2，不满足递增关系） * 第二步：通过第一步，我们可以得到一个子数组，区间为$[l,r]$，那么对应的上升子数组的长度则为区间长度$r-l+1$，我们以此更新最大值 * 第三步：将$l$指针移动到$r$指针的下一个位置，重复第一步和第二步，直到走到数组的最后一个位置。 整个过程如下面视频所示 C++ ```c++ #include<bits/stdc++.h> using namespace std; const int N=1E5+10; int n,w[N]; int main(){ cin>>n; for(int i=0;i<n;i++)cin>>w[i]; int res=0; //最大长度 for(int l=0;l<n;l++){ int r=l; while(r+1<n&&w[r+1]>w[r])r++; //r指针移动 res=max(res,r-l+1); //更新最大长度 l=r; } cout<<res<<endl; return 0; } ``` Java ```java import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int[] w = new int[n]; for (int i = 0; i < n; i++) { w[i] = scanner.nextInt(); } int res = 0; // 最大长度 for (int l = 0; l < n; l++) { int r = l; // 如果下一个元素大于当前元素，右边界向右移动 while (r + 1 < n && w[r + 1] > w[r]) { r++; } // 更新最大长度 res = Math.max(res, r - l + 1); l = r; } System.out.println(res); } } ``` Python ```python n = int(input()) w = list(map(int, input().split())) res = 0 # 最大长度 l = 0 while l < n: r = l # 如果下一个元素大于当前元素，右边界向右移动 while r + 1 < n and w[r + 1] > w[r]: r += 1 # 更新最大长度 res = max(res, r - l + 1) l = r + 1 print(res) ``` 最大值/最大长度 这一类题目，也是首先定义两个指针$l,r$，指向数组的起始位置 然后$r$指针先移动，移动到某一个区间，不满足条件的时候（比如题目要求区间和不大于某一个正整数，或者区间中元素$x$的个数$le k$）， 指针右移，直到满足条件。 然后满足条件的时候更新最大值/最大长度。下面提供模版代码，供大家参考。 C++ ```c++ bool check(){ // 这是一个示例的check函数，你需要根据实际情况来实现它 } int query(vector<int>&nums){ int n=nums.size(),res=0; //res为最大值/最大长度 for(int l=0,r=0;r<n;r++){ //定义两个指针l,r // ...省略代码，需要维护区间相关信息，例如区间和，或者区间某个元素数量 while(!check()){ //当前区间不满足条件 l++; //移动左指针 } res=max(res,cur); //更新最大值/最大长度 } return res; } ``` Java ```java import java.util.*; public class Main { public static int query(List<Integer> nums) { int n = nums.size(); int res = 0; // res为最大值/最大长度 for(int l=0,r=0;r<n;r++){ // 定义两个指针l,r // ...省略代码，需要维护区间相关信息，例如区间和，或者区间某个元素数量 while (!check()) { // 当前区间不满足条件 l++; // 移动左指针 } res = Math.max(res, cur); // 更新最大值/最大长度 } return res; } // 这是一个示例的check函数，你需要根据实际情况来实现它 public static boolean check() { // ...省略代码 return true; } } ``` Python ```python def query(nums): n = len(nums) res = 0 # res为最大值/最大长度 l = r = 0 # 定义两个指针l,r while r < n: # ...省略代码，需要维护区间相关信息，例如区间和，或者区间某个元素数量 while not check(): # 当前区间不满足条件 l += 1 # 移动左指针 res = max(res, cur) # 更新最大值/最大长度 r += 1 return res # 这是一个示例的check函数，你需要根据实际情况来实现它 def check(): # ...省略代码 return True ``` 最小值/最小长度 和上面最大值/最大长度的模版很像。 这一类题目，也是首先定义两个指针$l,r$，指向数组的起始位置 然后 指针先移动，移动到某一个区间，满足条件的时候（比如题目要求区间和大于某一个正整数，或者区间中元素$s$的个数$le k$）， 指针右移，直到不满足条件。 然后满足条件的时候更新最小值/最小长度。下面提供模版代码，供大家参考。 C++ ```c++ bool check(){ // 这是一个示例的check函数，你需要根据实际情况来实现它 } int query(vector<int>&nums){ int n=nums.size(),res=1e9; //res为最小值/最小长度 for(int l=0,r=0;r<n;r++){ //定义两个指针l,r // ...省略代码，需要维护区间相关信息，例如区间和，或者区间某个元素数量 while(check()){ //当前区间满足条件 res=min(res,cur); //更新最小值/最小长度 l++; //移动左指针 } } return res; } ``` Java ```java import java.util.*; public class Main { public static int query(List<Integer> nums) { int n = nums.size(); int res = 1e9; // res为最小值/最小长度 for(int l=0,r=0;r<n;r++){ // 定义两个指针l,r // ...省略代码，需要维护区间相关信息，例如区间和，或者区间某个元素数量 while (check()) { // 当前区间满足条件 res = Math.min(res, cur); // 更新最小值/最小长度 l++; // 移动左指针 } } return res; } // 这是一个示例的check函数，你需要根据实际情况来实现它 public static boolean check() { // ...省略代码 return true; } } ``` Python ```python def query(nums): n = len(nums) res = 109 # res为最小值/最小长度 l = r = 0 # 定义两个指针l,r while r < n: # ...省略代码，需要维护区间相关信息，例如区间和，或者区间某个元素数量 while check(): # 当前区间满足条件 res = min(res, cur) # 更新最大值/最大长度 l += 1 # 移动左指针 r += 1 return res # 这是一个示例的check函数，你需要根据实际情况来实现它 def check(): # ...省略代码 return True ``` 求方案数 这一类题目，一般是要求计算出满足题目条件的子数组的方案数，这个条件可能是：子数组和$le target$，子数组乘积$le k$等等，这种问题，首先我们考虑一个暴力求解的方式，那就是枚举所有可能的子数组，我们可以分别枚举子数组的左右两个端点，整体时间复杂度为$O(n^2)$，代码如下所示 C++ ```c++ int res=0; //方案数 for(int l=0;l<n;l++){ int sum=0; for(int r=l;r<n;r++){ sum+=w[r]; if(sum<=target){ res++; } } } cout<<res<<endl; ``` Java ```java int res = 0; // 方案数 for (int l = 0; l < n; l++) { int sum = 0; for (int r = l; r < n; r++) { sum += w[r]; if (sum <= target) { res++; } } } System.out.println(res); ``` Python ```python res = 0 # 方案数 for l in range(n): sum_val = 0 for r in range(l, n): sum_val += w[r] if sum_val <= target: res += 1 print(res) ``` 我们可以考虑一个优化的做法，首先这个做法的前提是子数组满足单调性，就是以$l$ 开头的子数组，子数组长度越长，区间和越大/区间元素累乘结果越大。然后我们可以定义两个双指针$l,r$，分别指向数组的起始位置，当$l,r$指向的区间不满足题目条件时，$l$指针右移，直到满足条件为止。当$[l,r]$区间满足条件时，由上述的单调性我们可知，区间$[r,r],[r-1,r],...,[l,r]$都是满足条件的，因此一共有$r-l+1$个区间满足条件，直接对方案数进行累加即可，然后继续移动$r$指针，直到移动到数组末尾。 C++ ```c++ bool check(){ // 这是一个示例的check函数，你需要根据实际情况来实现它 } int query(vector<int>&nums){ int n=nums.size(),res=0; //res为方案数 for(int l=0,r=0;r<n;r++){ //定义两个指针l,r // ...省略代码，需要维护区间相关信息，例如区间和，或者区间某个元素数量 while(!check()){ //当前区间不满足条件 l++; //移动左指针 } res+=r-l+1; //更新方案数 } return res; } ``` Java ```java public class Main { // 这是一个示例的check函数，你需要根据实际情况来实现它 public static boolean check() { // ...省略代码 return true; } public static int query(int[] nums) { int n = nums.length, res = 0; // res为方案数 for (int l = 0, r = 0; r < n; r++) { // 定义两个指针l,r // ...省略代码，需要维护区间相关信息，例如区间和，或者区间某个元素数量 while (!check()) { // 当前区间不满足条件 l++; // 移动左指针 } res += r - l + 1; // 更新方案数 } return res; } } ``` Python ```python def check(): # 这是一个示例的check函数，你需要根据实际情况来实现它 # ...省略代码 return True def query(nums): n = len(nums) res = 0 # res为方案数 l = r = 0 # 定义两个指针l,r # ...省略代码，需要维护区间相关信息，例如区间和，或者区间某个元素数量 while r < n: while not check(): # 当前区间不满足条件 l += 1 # 移动左指针 res += r - l + 1 # 更新方案数 r += 1 return res ``` 多指针滑动窗口 这类题型一般是有多个数组或者字符串，然后多个指针指向不同的数组或者字符串，这类题型最经典的问题就是判断子序列问题，很多题目都可以抽象成这样一个问题。 [LeetCode 392.判断子序列](https://leetcode.cn/problems/is-subsequence/) 难度系数：3 题解：本题是一个多指针题型的一个模板题，可以使用两个指针分别指向字符串`s`和`t`的起始位置，如果当前位置有`s[l]=t[r]`，则`l++`，`r++`，如果不相等，则`r++`，如果最终`l`指向字符串`s`的末尾位置，则说明字符串`s`是`t`的子序列。 复杂度分析 > 时间复杂度：$O(n+m)$ > > 空间复杂度：$O(1)$ C++ ```c++ bool isSubsequence(string s, string t) { int l=0,r=0; int n=s.size(),m=t.size(); while(l<n&&r<m) { if(s[l]==t[r]){ l++; } r++; } return l==n; } ``` Java ```java public boolean isSubsequence(String s, String t) { int l = 0, r = 0; int n = s.length(), m = t.length(); while (l < n && r < m) { if (s.charAt(l) == t.charAt(r)) { l++; } r++; } return l == n; } ``` Python3 ```python def isSubsequence(s, t): l, r = 0, 0 n, m = len(s), len(t) while l < n and r < m: if s[l] == t[r]: l += 1 r += 1 return l == n ``` [LeetCode 2410. 运动员和训练师的最大匹配数](https://leetcode.cn/problems/maximum-matching-of-players-with-trainers/description/) 难度系数：4 题解：排序+双指针，对于一个运动员`player[i]`来说，他应该尽可能匹配比他的数值大，且尽可能接近他的训练师`trainers[i]`，如果匹配的`trainers[i]`过大，会导致其他运动员可能无法匹配，因此我们可以直接把这两个数组排序，然后使用双指针模拟即可，和上面一道判断子序列的模板题的代码基本上一模一样，就是多了一个排序的代码。 复杂度分析 > 时间复杂度：$O(nlogn)$ > > 空间复杂度：$O(1)$ C++ ```c++ class Solution { public: int matchPlayersAndTrainers(vector<int>& players, vector<int>& trainers) { sort(players.begin(),players.end()); sort(trainers.begin(),trainers.end()); int n=players.size(),m=trainers.size(); int l=0,r=0; int res=0; while(l<n&&r<m){ if(players[l]<=trainers[r]){ l++; res++; } r++; } return res; } }; ``` Java ```java class Solution { public int matchPlayersAndTrainers(int[] players, int[] trainers) { Arrays.sort(players); Arrays.sort(trainers); int n = players.length; int m = trainers.length; int l = 0, r = 0; int res = 0; while (l < n && r < m) { if (players[l] <= trainers[r]) { l++; res++; } r++; } return res; } } ``` Python3 ```python class Solution: def matchPlayersAndTrainers(self, players, trainers): players.sort() trainers.sort() n = len(players) m = len(trainers) l = 0 r = 0 res = 0 while l < n and r < m: if players[l] <= trainers[r]: l += 1 res += 1 r += 1 return res ``` 不定长滑动窗口 这一类题目，滑动窗口的大小是不固定的，一般需要利用单调性去求最大/最小值 或者最长/最短的子串/子序列。 这种题目，很多可以使用双指针（一般都是同向双指针）求解的，也可以使用前缀和+哈希表来求解，而且前缀和+哈希表这种方法，即使不满足单调性，比如数组的数值为负数，也是可以求解的。是一个比较通用性的做法，在后续学习完前缀和+哈希表算法之后，可以回过头来把这几道题目在做一做~ [acwing 3722 骑车路线](https://www.acwing.com/problem/content/description/3725/) 难度系数：4 参考上述最长上升子数组的模版即可：[ 大厂笔试基础课](https://xuq7bkgch1.feishu.cn/docx/JtYJdUsBUofBKnx0X4EcJAuRnWh#part-R2tjdxIBnoMslKxx50pccKPdnzb) 本题有一个细节：要求的数组可以不满足严格递增，即只要有$w[i+1]ge w[i]$即可，这里需要注意一下，否则会爆WA 本题多组输入，大家需要注意一下，尤其是Python同学，要掌握处理这种输入的方式 后面大家学习到动态规划之后，也可以利用动态规划的状态转移方程来求解。但是利用动态规划来求解的空间复杂度较高，是$O(n)$的空间复杂度，不是最优解。 C++ ```c++ #include<bits/stdc++.h> using namespace std; const int N=1010; int n,p[N]; int main(){ while(~scanf("%d",&n)){ for(int i=0;i<n;i++)cin>>p[i]; int res=0; for(int l=0;l<n;l++){ int r=l; while(r+1<n&&p[r]<=p[r+1])r++; int len=r-l+1; //区间长度 if(len>=2){ res=max(res,p[r]-p[l]); } l=r; } cout<<res<<endl; } return 0; } ``` Java ```java import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); while (scanner.hasNextInt()) { int n = scanner.nextInt(); int[] p = new int[n]; for (int i = 0; i < n; i++) { p[i] = scanner.nextInt(); } int res = 0; for (int l = 0; l < n; l++) { int r = l; // 如果下一个元素大于等于当前元素，右边界向右移动 while (r + 1 < n && p[r] <= p[r + 1]) { r++; } int len = r - l + 1; // 区间长度 // 如果区间长度大于等于2，更新结果 if (len >= 2) { res = Math.max(res, p[r] - p[l]); } l = r; } System.out.println(res); } scanner.close(); } } ``` Python ```python while True: try: n = input() if not n: # 如果输入的是空字符串，跳出循环 break n = int(n) p = list(map(int, input().split())) res = 0 l = 0 while l < n: r = l # 如果下一个元素大于等于当前元素，右边界向右移动 while r + 1 < n and p[r] <= p[r + 1]: r += 1 len = r - l + 1 # 区间长度 # 如果区间长度大于等于2，更新结果 if len >= 2: res = max(res, p[r] - p[l]) l = r + 1 print(res) except EOFError: break ``` [LeetCode 1493. 删掉一个元素以后全为 1 的最长子数组](https://leetcode.cn/problems/longest-subarray-of-1s-after-deleting-one-element/description/) 难度系数：3 题解：双指针 首先观察数组，有这样一个特点：元素的值不是0就是1，那么则说明，该子数组的区间和是非递减的（对于从某一个位置开始的区间，区间长度越大，区间和越大），因此是满足单调性的（如果本题数组元素有负数，则不可以使用双指针算法求解），这里求解的是最大长度，因此可以使用上述双指针的第二个模版求解：[ 大厂笔试基础课](https://xuq7bkgch1.feishu.cn/docx/JtYJdUsBUofBKnx0X4EcJAuRnWh#part-R3uOd0PyroiSb9xTax5caaL5nFe) 由于只能删除一个元素，因此如果对于$[l,r]$区间中，如果含有超过 1 个的`0`元素，那么无论 指针怎么右移，这个区间都是不满足条件的，因此这个时候需要 指针右移，去除不合法的区间，对于$[l,r]$区间内的1的个数可以使用区间和$sum$来记录，如果$sum<r-l$，则说明区间含有 1 个以上的`0`元素。 复杂度分析 > 时间复杂度：$O(n)$ > > 空间复杂度：$O(1)$ C++ ```c++ class Solution { public: int longestSubarray(vector<int>& nums) { int res=0,n=nums.size(); for(int l=0,r=0,sum=0;r<n;r++){ sum+=nums[r]; while(sum<r-l){ sum-=nums[l++]; } res=max(res,r-l); } return res; } }; ``` Java ```java class Solution { public int longestSubarray(int[] nums) { int res = 0, n = nums.length; int sum = 0; for (int r = 0,l=0; r < n; r++) { sum += nums[r]; while (sum < r - l) { sum -= nums[l++]; } res = Math.max(res, r - l); } return res; } } ``` Python3 ```python class Solution: def longestSubarray(self, nums): res = 0 n = len(nums) sum_val = 0 l = 0 for r in range(n): sum_val += nums[r] while sum_val < r - l: sum_val -= nums[l] l += 1 res = max(res, r - l) return res ``` [LeetCode 1658. 将 x 减到 0 的最小操作数](https://leetcode.cn/problems/minimum-operations-to-reduce-x-to-zero/description/) 难度系数：4 题解：双指针+正难则反 本题可以从最左边和最右边选择一个数，将其对 作差，这样去思考的话，对应的区间是不连续的，但是我们反过来思考：最终剩下的区间一定是一段连续的区间。 我们定义数组的元素总和为$sum$，那么移除若干个元素之后剩下的区间和则为$sum-1$ 那么就把问题转换为：求一个最长的连续区间（因为要使得删除的元素最小化，则剩下的区间长度一定是最大的），使得其满足区间和等于$sum-1$，我们利用上述模版即可，和上一道LeetCode题基本上一模一样的思路，代码也差别不大。 本题需要特判一下：如果$sum< x$，则一定无解。 C++ ```c++ class Solution { public: int minOperations(vector<int>& nums, int x) { int total = accumulate(nums.begin(), nums.end(), 0); int target = total - x; // 将问题转化为区间和为target的最大长度 if (target < 0) { // 一定无解 return -1; } int n = nums.size(); int res = -1; // 将答案最大化 for(int l = 0, r = 0, sum_val = 0;r<n;r++) { // 定义左指针、右指针、区间和 sum_val += nums[r]; while (sum_val > target) { sum_val -= nums[l]; l++; } if (sum_val == target) { // 更新最大值 res = max(res, r - l + 1); } } if (res == -1) { return res; } return n - res; } }; ``` Java ```java public class Solution { public int minOperations(int[] nums, int x) { int total = Arrays.stream(nums).sum(); int target = total - x; // 将问题转化为区间和为target的最大长度 if (target < 0) { // 一定无解 return -1; } int n = nums.length; int res = -1; // 将答案最大化 for(int l = 0, r = 0, sum_val = 0;r<n;r++) { // 定义左指针、右指针、区间和 sum_val += nums[r]; while (sum_val > target) { sum_val -= nums[l]; l++; } if (sum_val == target) { // 更新最大值 res = Math.max(res, r - l + 1); } } if (res == -1) { return res; } return n - res; } } ``` Python ```python class Solution: def minOperations(self, nums: List[int], x: int) -> int: total=sum(nums) target=total-x #将问题转化为区间和为target的最大长度 if target<0: #一定无解 return -1 n=len(nums) res=-1 #将答案最大化 l,r,sum_val=0,0,0 #定义左指针、右指针、区间和 while r<n: sum_val+=nums[r] while sum_val>target: sum_val-=nums[l] l+=1 if sum_val==target: #更新最大值 res=max(res,r-l+1) r+=1 if res==-1: return res return n-res ``` [LeetCode 209. 长度最小的子数组](https://leetcode.cn/problems/minimum-size-subarray-sum/description/) 难度系数：3 题解：双指针 首先注意到，数组所有的元素都是正整数，这说明该子数组的区间和是非递减的（对于从某一个位置开始的区间，区间长度越大，区间和越大），因此是满足单调性的（如果本题数组元素有负数，则不可以使用双指针算法求解），这里求解的是最小长度，因此可以使用上述双指针的第三个模版求解：[ 大厂笔试基础课](https://xuq7bkgch1.feishu.cn/docx/JtYJdUsBUofBKnx0X4EcJAuRnWh#part-GbhodJeL3oP7Vax122lczDxXnhd) 我们定义两个指针$l,r$，当$[l,r]$构成的区间和满足$ge target$时，我们可以更新最小长度，并移动左指针，直到不满足条件为止，当不满足条件时， 指针继续向右移动。 C++ ```c++ class Solution { public: int minSubArrayLen(int target, vector<int>& nums) { int n=nums.size(),res=1e9; for(int l=0,r=0,sum=0;r<n;r++){ //定义双指针l,r,区间和sum sum+=nums[r]; while(sum>=target){ //当前区间满足条件，更新最小值 res=min(res,r-l+1); sum-=nums[l]; l++; } } return (res==1e9)?0:res; } }; ``` Java ```java public class Solution { public int minSubArrayLen(int target, int[] nums) { int n = nums.length; int res = Integer.MAX_VALUE; // 初始化结果为最大整数 int l = 0, r = 0, sum = 0; // 定义双指针l,r,区间和sum for (; r < n; r++) { // 右指针向右移动 sum += nums[r]; while (sum >= target) { // 当前区间满足条件，更新最小值 res = Math.min(res, r - l + 1); sum -= nums[l]; l++; // 左指针向右移动 } } return (res == Integer.MAX_VALUE) ? 0 : res; // 如果结果仍为最大整数，说明没有满足条件的子数组，返回0 } } ``` Python ```python class Solution: def minSubArrayLen(self, target: int, nums: List[int]) -> int: n = len(nums) res = float('inf') # 初始化结果为无穷大 l = r = sum_val = 0 # 定义双指针l,r,区间和sum_val for r in range(n): # 右指针向右移动 sum_val += nums[r] while sum_val >= target: # 当前区间满足条件，更新最小值 res = min(res, r - l + 1) sum_val -= nums[l] l += 1 # 左指针向右移动 return 0 if res == float('inf') else res # 如果结果仍为无穷大，说明没有满足条件的子数组，返回0 ``` [acwing 3624. 三值字符串](https://www.acwing.com/problem/content/description/3627/) 难度系数：4 题解：双指针 与上面的LeetCode 209，同属于求最小长度的双指针题型，我们定义两个指针$l,r$，分别指向字符串的初始位置，然后维护一个长度为3的数组，分别记录字符1,2,3的数量，当区间内的三种字符的数量都$ge 1$时，我们可以移动左指针 ，同时更新答案的最小值，当区间不满足条件时，停止移动左指针 ，继续向右移动右指针 ，直到遍历到字符串的最后一个位置。 C++ ```c++ #include<bits/stdc++.h> using namespace std; int T; void solve(){ string s; cin>>s; int n=s.size(); vector<int>cnts(3,0); //分别统计1,2,3字符的个数 int res=n+1; //初始化最小值 for(int l=0,r=0;r<n;r++){ cnts[s[r]-'1']++; while(cnts[0]>0&&cnts[1]>0&&cnts[2]>0){ //区间同时包含字符1,2,3 res=min(res,r-l+1); cnts[s[l]-'1']--; l++; } } if(res==n+1)puts("0"); else cout<<res<<endl; } int main(){ cin>>T; while(T--){ solve(); } return 0; } ``` Java ```java import java.util.*; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int T = scanner.nextInt(); while (T-- > 0) { solve(scanner); } } public static void solve(Scanner scanner) { String s = scanner.next(); int n = s.length(); int[] cnts = new int[3]; // 分别统计1,2,3字符的个数 int res = n + 1; // 初始化最小值 for (int l = 0, r = 0; r < n; r++) { cnts[s.charAt(r) - '1']++; while (cnts[0] > 0 && cnts[1] > 0 && cnts[2] > 0) { // 区间同时包含字符1,2,3 res = Math.min(res, r - l + 1); cnts[s.charAt(l) - '1']--; l++; } } if (res == n + 1) { System.out.println("0"); } else { System.out.println(res); } } } ``` Python ```python def solve(): s = input().strip() n = len(s) cnts = [0, 0, 0] # 分别统计1,2,3字符的个数 res = n + 1 # 初始化最小值 l = r = 0 while r < n: cnts[ord(s[r]) - ord('1')] += 1 while cnts[0] > 0 and cnts[1] > 0 and cnts[2] > 0: # 区间同时包含字符1,2,3 res = min(res, r - l + 1) cnts[ord(s[l]) - ord('1')] -= 1 l += 1 r += 1 print("0" if res == n + 1 else res) T = int(input().strip()) for _ in range(T): solve() ``` [LeetCode 713. 乘积小于 K 的子数组](https://leetcode.cn/problems/subarray-product-less-than-k/) 难度系数：4 题解：双指针 双指针求方案数，不太熟悉的同学可以参考双指针算法模版的第四个模版：[ 大厂笔试基础课](https://xuq7bkgch1.feishu.cn/docx/JtYJdUsBUofBKnx0X4EcJAuRnWh#part-SGvUdRSVoozzACxZ93Acxyjjn2b)。注意到题目给的数组元素$nums[i]$都是正整数，因此满足单调性，可以使用双指针来求解。 我们定义两个指针$l,r$分别指向数组的起始位置，并维护$l,r$指向的区间的乘积值，如果对应区间的乘积值$ge k$，则说明区间不满足条件，因此需要移动$l$指针，直到满足题目条件，满足题目条件时，我们需要对方案数加上$r-l+1$。 本题有一个地方需要注意：当$ kle 1$时，由于数组元素都是正整数，因此任意一个区间的元素乘积都是不满足$< k$的，因此直接返回0即可。 C++ ```c++ class Solution { public: int numSubarrayProductLessThanK(vector<int>& nums, int k) { int n=nums.size(),res=0; if(k<=1)return 0; for(int l=0,r=0,total=1;r<n;r++){ total*=nums[r]; while(total>=k){ //当前区间不满足条件，l左移 total/=nums[l]; l++; } res+=r-l+1; //[l,r]区间有r-l+1个子区间都满足题意 } return res; } }; ``` Java ```java public class Solution { public int numSubarrayProductLessThanK(int[] nums, int k) { int n = nums.length, res = 0; if (k <= 1) return 0; int l = 0, r = 0, total = 1; for (; r < n; r++) { total *= nums[r]; while (total >= k) { // 当前区间不满足条件，l左移 total /= nums[l]; l++; } res += r - l + 1; // [l,r]区间有r-l+1个子区间都满足题意 } return res; } } ``` Python ```python class Solution: def numSubarrayProductLessThanK(self, nums, k): n = len(nums) res = 0 if k <= 1: return 0 l = 0 total = 1 for r in range(n): total *= nums[r] while total >= k: # 当前区间不满足条件，l左移 total /= nums[l] l += 1 res += r - l + 1 # [l,r]区间有r-l+1个子区间都满足题意 return res ``` [LeetCode 2302. 统计得分小于 K 的子数组数目](https://leetcode.cn/problems/count-subarrays-with-score-less-than-k/) 难度系数：5 题解：双指针 本题作为一个LeetCode Hard题，看起来很唬人，其实是一个纸老虎，用双指针的第四个模版即可轻松AC 我们定义两个指针$l,r$分别指向数组的起始位置，并使用一个变量$sum$来维护$[l,r]$区间的区间和，那么数组的分数就可以用$sum imes (r-l+1)$来计算出，然后如果当前子数组的分数不满足条件，即$sum imes (r-l+1)ge k$ ,则需要移动$l$指针来减少子数组的分数，如果当前子数组的分数满足条件，则把当前答案加上$r-l+1$。代码和上面的LeetCode 713基本上一模一样。 C++ ```c++ class Solution { public: long long countSubarrays(vector<int>& nums, long long k) { long long res=0,sum=0; int n=nums.size(); for(int l=0,r=0;r<n;r++){ sum+=nums[r]; while(sum*(r-l+1)>=k){ //当前区间不满足条件,l指针右移 sum-=nums[l]; l++; } res+=r-l+1; } return res; } }; ``` Java ```java public class Solution { public long countSubarrays(int[] nums, long k) { long res = 0, sum = 0; int n = nums.length; for (int l = 0, r = 0; r < n; r++) { sum += nums[r]; while (sum * (r - l + 1) >= k) { // 当前区间不满足条件,l指针右移 sum -= nums[l]; l++; } res += r - l + 1; } return res; } } ``` Python ```python class Solution: def countSubarrays(self, nums, k): res = sum_val = 0 n = len(nums) l = r = 0 while r < n: sum_val += nums[r] while sum_val * (r - l + 1) >= k: # 当前区间不满足条件,l指针右移 sum_val -= nums[l] l += 1 res += r - l + 1 r += 1 return res ``` [数组的删除方案](http://121.196.235.151/p/P1004) 难度系数：6 题解：双指针 首先我们考虑，删除区间的长度越短，则剩余数字的乘积越大，乘积越大，则说明其末尾0的个数越多（至少不会减少），因此是符合单调性的，可以考虑使用双指针算法求解。 末尾0的个数是什么呢？这个很重要，其实就是一个数字中因子$1$的个数，例如300有2个0,300可以看成$300=3 imes 10^2$，但是由于10不是质数，它有两个质因子2和5，因此问题就转换为一个数字中因子2和因子5个数的最小值，比如$60=2^2 imes 3 imes 5^1$，因此60的末尾0为$min(1,2)=1$ 本题我们需要去统计有多少删除方案，其实到了这一步问题就和上面的LeetCode 713和LeetCode 2302这两道题相同了，假设我们找到了一个区间$[l,r]$，删除这个区间可以使得剩余元素的乘积满足条件，那么对于区间$[r,r],[r-1,r],...,[l,r]$，都是满足条件的，因此对应的方案数为区间长度$r-l+1$ 如果区间长度$[l,r]$过大，导致剩余元素不满足条件，则需要移动左指针。 本题check函数细节：由于是删除操作，不是选择某个区间，因此我们首先需要去统计整个数组乘积的因子2和因子5的数量，分别记为$cnt2,cnt5$，然后当我们移动 $r$指针的时候，就需要减去当前$w[r]$的因子2和因子5的个数，如果当前区间不满足$min(cnt2,cnt5)ge k $，则需要移动`l`指针。 时间复杂度分析 预处理因子2和因子5的时间复杂度为$O(nlogn)$ 双指针计算方案数的时间复杂度为$O(n)$ 整体时间复杂度：$O(2 imes nlogn+n)$ C++ ```c++ #include <bits/stdc++.h> using namespace std; int main() { int n, k; cin >> n >> k; // 统计a[i]的因子2的数量 vector<int> a2(n, 0); // 统计a[i]的因子5的数量 vector<int> a5(n, 0); vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; // 计算每个数的因子2和因子5的数量 while (a[i] % 2 == 0) { a[i] /= 2; a2[i]++; } while (a[i] % 5 == 0) { a[i] /= 5; a5[i]++; } } int cnt2 = accumulate(a2.begin(), a2.end(), 0); // 因子2的总数量 int cnt5 = accumulate(a5.begin(), a5.end(), 0); // 因子5的总数量 int left = 0; long long ans = 0; // 使用滑动窗口计算满足条件的子数组数量 for (int right = 0; right < n; right++) { cnt2 -= a2[right]; cnt5 -= a5[right]; // 当前区间不满足条件（因子2和因子5的数量都小于k） while (left <= right && min(cnt2, cnt5) < k) { cnt2 += a2[left]; // 移动左指针，增加因子2的数量 cnt5 += a5[left]; // 移动左指针，增加因子5的数量 left++; } ans += right - left + 1; } cout << ans << endl; return 0; } ``` Java ```java import java.util.*; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int k = scanner.nextInt(); // 统计a[i]的因子2的数量 int[] a2 = new int[n]; // 统计a[i]的因子5的数量 int[] a5 = new int[n]; int[] a = new int[n]; for (int i = 0; i < n; i++) { a[i] = scanner.nextInt(); // 计算每个数的因子2和因子5的数量 while (a[i] % 2 == 0) { a[i] /= 2; a2[i]++; } while (a[i] % 5 == 0) { a[i] /= 5; a5[i]++; } } int cnt2 = Arrays.stream(a2).sum(); // 因子2的总数量 int cnt5 = Arrays.stream(a5).sum(); // 因子5的总数量 int left = 0; long ans = 0; // 使用滑动窗口计算满足条件的子数组数量 for (int right = 0; right < n; right++) { cnt2 -= a2[right]; cnt5 -= a5[right]; // 当前区间不满足条件（因子2和因子5的数量都小于k） while (left <= right && Math.min(cnt2, cnt5) < k) { cnt2 += a2[left]; // 移动左指针，增加因子2的数量 cnt5 += a5[left]; // 移动左指针，增加因子5的数量 left++; } ans += right - left + 1; } System.out.println(ans); } } ``` Python ```python n, k = list(map(int, input().split())) # 统计a[i]的因子2的数量 a2 = [0] * n # 统计a[i]的因子5的数量 a5 = [0] * n a = list(map(int, input().split())) # 计算每个数的因子2和因子5的数量 for i in range(n): while a[i] % 2 == 0: a[i] //= 2 a2[i] += 1 while a[i] % 5 == 0: a[i] //= 5 a5[i] += 1 cnt2 = sum(a2) # 因子2的总数量 cnt5 = sum(a5) # 因子5的总数量 left = 0 ans = 0 # 使用滑动窗口计算满足条件的子数组数量 for right in range(n): cnt2 -= a2[right] cnt5 -= a5[right] while left <= right and min(cnt2, cnt5) < k: #当前区间不满足条件（因子2和因子5的数量都小于k） cnt2 += a2[left] # 移动左指针，增加因子2的数量 cnt5 += a5[left] # 移动左指针，增加因子5的数量 left += 1 ans += right - left + 1 print(ans) ``` 哈希表 数据结构讲解 笔试和面试中经常用到的的一个数据结构，它是由多个`key-value`对来组成的，它有两个重要性质 * 性质1：哈希表中的`key`都是不重复的，因此可以用来进行去重操作 * 性质2：可以在$O(1$的时间内根据`key`得到`value`的值，因此也可以使用哈希表来记录元素的出现次数 对于`key-value`对来说，`value`一般用来表示`key`的出现次数，在`C++`中，哈希表通常使用 `unordered_map` 或 `unordered_set` 容器来实现，在`Java`中，哈希表通常使用 `HashMap` 或 `HashSet` 来实现，在`Python3`中，使用字典（`dict`）来实现哈希表。 哈希表还可以去帮助实现离散化：差分专题中的离散化差分就是借助有序的哈希表来实现的，有序哈希表指的是`key`有序，而不是`value`有序，`key`是按照从小到大递增存储的，因此遍历有序哈希表的`key`是递增的。 `C++`中的有序哈希表是`set`或者`map`来实现的，`Java`中的有序哈希表是使用`TreeMap`来实现的，`Python3`中默认的就是有序哈希表，因此可以直接使用`dict` 笔试中单独考察哈希表的题目较少，因此这里找的几道题目，主要是为了帮助大家更好地熟悉和使用哈希表 [acwing 4716 进球](https://www.acwing.com/problem/content/4719/) 难度系数：2 题解：哈希表 我们可以使用哈希表来去记录每一支球队的进球次数，`key-value`对中，`key`表示球队名称，用字符串来表示，`value`表示该球队的进球次数，用`int`型变量表示。 统计完之后，我们可以遍历这个哈希表，然后定义两个变量`res`和`cnt_max`，分别表示当前最大进球次数的球队名称和对应的最大进球次数，然后一边遍历一边更新即可。 C++ ```c++ #include<bits/stdc++.h> using namespace std; int main(){ int n; string s; cin>>n; unordered_map<string,int>cnts; //统计每一支球队的进球次数 while(n--){ cin>>s; cnts[s]++; //哈希表计数+1 } string res; int cnt_max=0; for(auto &[u,v]:cnts){ //遍历哈希表,查询出进球次数最大的球队 if(v>cnt_max){ res=u; cnt_max=v; } } cout<<res<<endl; return 0; } ``` Java ```java import java.util.*; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scannerjava数据结构基础题型及解法.nextInt(); Map<String, Integer> cnts = new HashMap<>(); // 统计每一支球队的进球次数 while (n-- > 0) { String s = scanner.next(); cnts.put(s, cnts.getOrDefault(s, 0) + 1); // 哈希表计数+1 } String res = ""; int cnt_max = 0; for (Map.Entry<String, Integer> entry : cnts.entrySet()) { // 遍历哈希表,查询出进球次数最大的球队 if (entry.getValue() > cnt_max) { res = entry.getKey(); cnt_max = entry.getValue(); } } System.out.println(res); } } ``` Python ```python n = int(input()) cnts = {} # 统计每一支球队的进球次数 for _ in range(n): s = input() cnts[s] = cnts.get(s, 0) + 1 # 哈希表计数+1 res = max(cnts, key=cnts.get) # 遍历哈希表,查询出进球次数最大的球队 print(res) ``` [数组的最大权值](http://121.196.235.151/p/P1002) 难度系数：2 题解：哈希表 贪心 对于选定的 个数字，我们一定是尽可能选择互不相等的 个数字，才可以使得其权值最大。 我们可以使用集合（`set`）这种数据结构来对数组的元素进行去重，最终得到集合的大小（也就是数组中互不相同的元素个数）为$siz$，那么所能得到的最大权值一定是$siz$和 取最小值$min(size,k)$ C++ ```c++ #include<bits/stdc++.h> using namespace std; const int N=1E5+10; int n,k,a[N]; int main(){ cin>>n>>k; unordered_set<int>st; for(int i=0;i<n;i++){ int x; cin>>x; st.insert(x); } int res=min(k,(int)st.size()); cout<<res<<endl; return 0; } ``` Java ```java import java.util.*; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int k = scanner.nextInt(); Set<Integer> st = new HashSet<>(); for (int i = 0; i < n; i++) { int x = scanner.nextInt(); st.add(x); } int res = Math.min(k, st.size()); System.out.println(res); } } ``` Python ```python import sys input = lambda:sys.stdin.readline().strip() n, k = map(int, input().split()) s = set(list(map(int, input().split()))) print(min(k, len(s)) ``` [LeetCode 2653. 滑动子数组的美丽值](https://leetcode.cn/problems/sliding-subarray-beauty/description/) 难度系数：5 题解：哈希表+双指针 首先，题目需要求每一个长度为 的区间的“美丽值”，这显然可以使用双指针算法来求解，并且由于区间长度固定，这是一个很简单的定长滑动窗口问题。本题的难点在于，如何找到每一个区间中第 小的数，并判断其是不是负数。 本题有一个很重要的条件：数组中所有的元素范围为$-50le nums[i]le 50$ 那么，我们可以使用哈希表来统计固定长度的区间中每个元素出现的次数，然后从小到大枚举$nums[i]$的值（本题只需要枚举$[-50,-1]$的值），并对这些数字出现的次数，使用一个变量$cnt$来记录，当枚举到数字 ，且有$ cntge x $ 时，则说明当前数字$i$是第 $x$小的数字。如果枚举了所有负数出现的次数，都不满足$cntle x $，则说明该区间的美丽值为0。 时间复杂度 $O(n imes V)$，其中 为数组长度，$nle 10^5$， 为元素的值域，$Vle 50$（因为只需要枚举负数） C++ ```c++ class Solution { public: vector<int> getSubarrayBeauty(vector<int>& nums, int k, int x) { unordered_map<int,int>cnts; vector<int>res; int n=nums.size(); for(int l=0,r=0;r<n;r++){ cnts[nums[r]]++; if(r-l+1>k){ //当前窗口大小>k 左指针右移 cnts[nums[l]]--; l++; } if(r-l+1==k){ //找到一个长度为k的区间 int cnt=0; //统计区间内的负数数量 for(int i=-50;i<0;i++){ if(cnts.count(i)){ cnt+=cnts[i]; } if(cnt>=x){ //如果当前的负数数量已经>=x,说明当前数字i就是第x小的数字 res.push_back(i); break; } } if(cnt<x){ res.push_back(0); } } } return res; } }; ``` Java ```java class Solution { public int[] getSubarrayBeauty(int[] nums, int k, int x) { Map<Integer, Integer> cnts = new HashMap<>(); List<Integer> resList = new ArrayList<>(); int n = nums.length; for (int l = 0, r = 0; r < n; r++) { cnts.put(nums[r], cnts.getOrDefault(nums[r], 0) + 1); if (r - l + 1 > k) { // 当前窗口大小>k 左指针右移 cnts.put(nums[l], cnts.get(nums[l]) - 1); l++; } if (r - l + 1 == k) { // 找到一个长度为k的区间 int cnt = 0; // 统计区间内的负数数量 for (int i = -50; i < 0; i++) { if (cnts.containsKey(i)) { cnt += cnts.get(i); } if (cnt >= x) { // 如果当前的负数数量已经>=x,说明当前数字i就是第x小的数字 resList.add(i); break; } } if (cnt < x) { resList.add(0); } } } // 将结果List转换为数组 int[] res = new int[resList.size()]; for (int i = 0; i < resList.size(); i++) { res[i] = resList.get(i); } return res; } } ``` Python ```python class Solution: def getSubarrayBeauty(self, nums, k, x): cnts = {} res = [] n = len(nums) l = r = 0 while r < n: cnts[nums[r]] = cnts.get(nums[r], 0) + 1 if r - l + 1 > k: # 当前窗口大小>k 左指针右移 cnts[nums[l]] -= 1 l += 1 if r - l + 1 == k: # 找到一个长度为k的区间 cnt = 0 # 统计区间内的负数数量 for i in range(-50, 0): if i in cnts: cnt += cnts[i] if cnt >= x: # 如果当前的负数数量已经>=x,说明当前数字i就是第x小的数字 res.append(i) break if cnt < x: res.append(0) r += 1 return res ``` [acwing 3771. 选取石子](https://www.acwing.com/problem/content/description/3774/) 难度系数：5 题解：哈希表+分组 本题的样例有些问题，这里其实想举得例子应该是三个石子的价值分别为2,4,6 ![](images/image-1.png) 本题其实可以抽象为：如何将石子按照条件分组，使得组内所有石子的价值总和最大。 对于相邻两个石子需要满足$x-y=a_x-a_x$，我们把$x$和$y$移动到等式一段，则可以得到$a_x-x=a_y-y$，我们不难看出，组内的石子按照从小到大排序可以得到一个递增的等差数列，也就是所有满足$a_x-x=t$（$t$为定值）均可以被分到一组，作为一种选择方案。 因此，我们可以使用哈希表来存不同$t$值对应的石子价值总和，然后遍历哈希表来更新最大价值即可。 时间复杂度分析： $t=a_i-i$，其中$1le a_ile 4 imes 10^5,1le ile n$，因此，$1-2 imes 10^5le tle 4 imes 10^5-1$ 我们遍历所有可能得$t$，最坏情况也不会超过$6 imes 10^5$，完全可以在1s内运行。 注意：本题价值可能会爆`int`，因此对于C++和Java选手，需要使用`long long`来存最终的价值。 例如，数组是一个长度为$2 imes 10^5$，首项为2，公差为2的等差数列，那么对应的最大价值就是整个数组的和，即为$frac{(a_1+a_n)}{2} imes n=frac{(2+2 imes 10^5)}{2} imes2 imes 10^5 approx 10^{10}>2^{31}-1$ C++ ```c++ #include<bits/stdc++.h> using namespace std; const int N=4E5+10; int n,a[N]; int main(){ unordered_map<int,long long>mp; //记录每个分组的最大价值 cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; mp[a[i]-i]+=a[i]; //当前分组加入价值a[i]的石头 } long long res=0; //最大价值 for(auto &[u,v]:mp){ //遍历哈希表 res=max(res,v); } cout<<res<<endl; return 0; } ``` Java ```java import java.util.*; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int[] a = new int[n + 1]; Map<Integer, Long> mp = new HashMap<>(); // 记录每个分组的最大价值 for (int i = 1; i <= n; i++) { a[i] = scanner.nextInt(); mp.put(a[i] - i, mp.getOrDefault(a[i] - i, 0L) + a[i]); // 当前分组加入价值a[i]的石头 } long res = 0; // 最大价值 for (long v : mp.values()) { // 遍历哈希表 res = Math.max(res, v); } System.out.println(res); } } ``` Python ```python n = int(input()) a = [0] + list(map(int, input().split())) mp = {} # 记录每个分组的最大价值 for i in range(1, n + 1): mp[a[i] - i] = mp.get(a[i] - i, 0) + a[i] # 当前分组加入价值a[i]的石头 res = 0 # 最大价值 for v in mp.values(): # 遍历哈希表 res = max(res, v) print(res) ``` 前缀和 算法讲解 前缀和算法，是用来快速求解数组中某一个区间的区间和的值，如果对于每一个询问，都可以在$O(1)$的时间复杂度内快速求解，如果使用枚举的思想，则平均复杂度为$O(n)$，远高于$O(1)$的复杂度，那么前缀和是如何做到这一点的，其实是通过区间拆分+预处理的思想得到的，预处理的复杂度为$O(n)$ 算法步骤 对于给定的一个数组，如下图所示，其中，0~8为数组的下标 ![](images/image-2.png) 那么，对于数组任意的一个区间范围$[i,j]$，如何快速地求解它的区间和？ 首先，我们可以看几个例子 $[0,2]$的区间和为$w[0]+w[1]+w[2]=1+2+4=7$ $[1,3]$的区间和为$w[1]+w[2]+w[3]=2+4+5=11$ 我们可以预处理一个前缀和数组 ，其中$s[i]$表示区间$[0,i]$的区间和，那么我们很容易得出$s[i]$的递推式 $s[i]=s[i-1]+w[i],s[0]=w[0]$ 根据上述式子，我们可以得到一个前缀和数组，如下图所示 ![](images/image-3.png) 我们知道，对于区间$[0,i]$的前缀和为$s[i]$，区间$[0,j]$的前缀和为$s[j]$，则区间$[j,i]$的前缀和为$s[i]-s[j-1]$，具体计算方式如下： $[j:i]区间和=w[i]+w[i+1]+...w[j]$ $s[i]=w[0]+w[1]+...w[i]$ $s[j-1]=w[0]+w[1]+...+w[j-1]$ $[j:i]区间和=s[i]-s[j-1]$ 因此，我们只需要预处理出前缀和数组，就可以根据上述计算公式，快速地计算出任意一个区间的区间和，在实际笔试或者面试中，为了减少边界情况的考虑，我们更习惯性地将数组下标设置为从1开始。 使用场景 * 一维前缀和主要是用于快速地求解某一个区间和，但是前缀和是静态的算法，就是说这个数组中每一个元素的值不能被修改，如果要一边修改一边动态查询，就需要使用树状数组或者线段树这种数据结构来实现动态查询。 * 二维前缀和主要是针对二维场景，比如对于一个矩阵，矩阵的长度为 ，宽度为 ，它对应有$n*$个整数点，每一个点对应的权值不同，使用二维前缀和可以快速求出起点为$(x1,y1$，终点为$(x2,y2$的小矩形的权值和。 注意：本算法一般是基础算法，笔试中除了单独考察之外，很多时候会结合哈希表，动态规划，贪心等算法综合考察。 算法模版 一维前缀和 题目描述 输入一个长度为`n`的整数序列。 接下来再输入`m`个询问，每个询问输入一对`l,r` 对于每个询问，输出原序列中从第`l`个数到第`r`个数的和。 输入格式 > 第一行包含两个整数`n`和`m`。 > > 第二行包含`n`个整数，表示整数数列。 > > 接下来`m` 行，每行包含两个整数`l` 和`r`，表示一个询问的区间范围。 输出格式 > 共`m`行，每行输出一个询问的结果。 数据范围 > $1le lle rle $ > > $1le n,m le 10^5$ > > $-10^3le 数列中元素的值 le 10^3$ 输入样例 ```plain&#x20;text 5 3 2 1 3 6 4 1 2 1 3 2 4 ``` 输出样例 ```plain&#x20;text 3 6 10 ``` 题解：前缀和模板题，大家直接把这个板子背过就行，笔试中遇到就直接套用即可 C++ ```c++ #include <iostream> using namespace std; const int N = 1e+6 + 10; int a[N], S[N],n,m; int main() { cin>>n>>m; for(int i = 1; i <= n; i++)cin>>a[i]; for(int i=1;i<=n;i++) S[i]=S[i-1]+a[i]; while (m--) { int l;int r; cin>>l>>r; printf("%d ",S[r]-S[l-1]); } return 0; } ``` Java ```java import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = ; int[] a = new int[N]; int[] S = new int[N]; int n = sc.nextInt(); int m = sc.nextInt(); for (int i = 1; i <= n; i++) { a[i] = sc.nextInt(); S[i] = S[i - 1] + a[i]; } while (m-- > 0) { int l = sc.nextInt(); int r = sc.nextInt(); System.out.println(S[r] - S[l - 1]); } sc.close(); } } ``` Python3 ```python n, m = map(int, input().split()) a = [0] * (n + 1) S = [0] * (n + 1) a[1:n + 1] = map(int, input().split()) for i in range(1, n + 1): S[i] = S[i - 1] + a[i] for _ in range(m): l, r = map(int, input().split()) print(S[r] - S[l - 1]) ``` 二维前缀和 题目描述 输入一个$n$行 $m$列的整数矩阵，再输入$q$个询问，每个询问包含四个整数 $x1,y1,x2,y2$，表示一个子矩阵的左上角坐标和右下角坐标。 对于每个询问输出子矩阵中所有数的和。 输入格式 第一行包含三个整数 $n,m,q$。 接下来 $n$行，每行包含 个整数，表示整数矩阵。 接下来 $q$行，每行包含四个整数 $x1,y1,x2,y2$，表示一组询问。 输出格式 共 $q$行，每行输出一个询问的结果。 数据范围 $1le n,n le 1000$ $1le q le 2*10^5$ $1le x1le x2le n$ $1le y1 le y2 le m$ $−100le 矩阵内元素的le 100$ 输入样例 ```plain&#x20;text 3 4 3 1 7 2 4 3 6 2 8 2 1 2 3 1 1 2 2 2 1 3 4 1 3 3 4 ``` 输出样例 ```plain&#x20;text 17 27 21 ``` 二维前缀和模板题，这里给大家提供多语言版本的代码模版，大家背过就行，笔试的时候直接拿出来用即可。 C++ ```c++ #include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 1010; int n, m, q; int a[N][N], s[N][N]; int main() { cin >> n >> m >> q; for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= m; j ++ ) cin >> a[i][j], s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + a[i][j]; while (q -- ) { int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; cout << s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1] << endl; } return 0; } ``` Java ```java import java.util.Scanner; public class Main{ public static void main(String[] args){ Scanner scan = new Scanner(System.in); int n = scan.nextInt(); int m = scan.nextInt(); int q = scan.nextInt(); int[][] a = new int[n+1][m+1]; int[][] s = new int[n+1][m+1]; for(int i = 1 ; i <= n ; i ++ ){ for(int j = 1 ;j <= m ; j ++ ){ a[i][j] = scan.nextInt(); } } for(int i = 1 ; i <= n ; i ++ ){ for(int j = 1 ;j <= m ; j ++ ){ s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j]; } } while(q-->0){ int x1 = scan.nextInt(); int y1 = scan.nextInt(); int x2 = scan.nextInt(); int y2 = scan.nextInt(); System.out.println(s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]); } } } ``` Python ```python N = 1010 a = [[0]*N for _ in range(N)] s = [[0]*N for _ in range(N)] n,m,q = map(int,input().split()) for i in range(1,n+1): a[i] = [0] + list(map(int,input().split())) + a[m+1:] for i in range(1,n+1): for j in range(1,m+1): s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j] while q: x1,y1,x2,y2 = map(int,input().split()) print(s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]) q -= 1 ``` 朴素前缀和 这一类题型，一般都是单独对前缀和进行考察，因此只需要把题目抽象为前缀和问题，并利用上述一维或者二维的前缀和模版即可AC。 [求区间和](http://121.196.235.151/p/P1014) 难度系数：3 题解：一维前缀和模板题 本题直接将上述一维前缀和的算法模版，直接copy过来，改一下输入的处理即可AC。 C++ ```c++ #include <iostream> using namespace std; const int N = 1e+6 + 10; int a[N], S[N],n,m; int main() { cin>>n; for(int i = 1; i <= n; i++)cin>>a[i]; for(int i=1;i<=n;i++) S[i]=S[i-1]+a[i]; cin>>m; while (m--) { int l;int r; cin>>l>>r; cout<<S[r]-S[l-1]<<endl; } return 0; } ``` Java ```java import java.util.*; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int[] a = new int[n + 1]; int[] S = new int[n + 1]; for (int i = 1; i <= n; i++) { a[i] = scanner.nextInt(); S[i] = S[i - 1] + a[i]; // 计算前缀和 } int m = scanner.nextInt(); while (m-- > 0) { int l = scanner.nextInt(); int r = scanner.nextInt(); System.out.println(S[r] - S[l - 1]); // 输出区间和 } } } ``` Python ```python n = int(input()) a = [0] + list(map(int, input().split())) S = [0] * (n + 1) for i in range(1, n + 1): S[i] = S[i - 1] + a[i] # 计算前缀和 m = int(input()) for _ in range(m): l, r = map(int, input().split()) print(S[r] - S[l - 1]) # 输出区间和 ``` [三倍数](http://121.196.235.151/p/P1005) 难度系数：3 题解：一维前缀和+简单数学 根据小学数学我们可以知道，对于一个数字 ，它是3的倍数的充要条件就是它的数位之和是3的倍数，例如72的数位之和为7+2=9，是3的倍数，因此72是3的倍数。 因此，我们可以使用前缀和数组$s[i]$预处理区间$[1,i]$的数位之和（比如123的数位之和=1+2+3=6） 然后对于每一个查询$[l,r]$，我们可以利用$s[r]-s[l-1]$来在$O(1)$的时间内计算出区间的数位之和，具体参考下面代码 对于一个数字 ，预处理它的数位之和的时间复杂度为$log_{10}(x)$ 因此总的时间复杂度为$O(n imes 9+q)$，9是因为$a_ile 10^9$，因此预处理数位之和的时间复杂度不会超过$O(n imes 9)$ C++ ```c++ #include<bits/stdc++.h> using namespace std; const int N=1E5+10; int n,q,s[N]; int f(int x){ //预处理数位之和 int res=0; while(x){ res+=x%10; x/=10; } return res; } int main(){ cin>>n>>q; for(int i=1;i<=n;i++){ int x; cin>>x; s[i]=s[i-1]+f(x); } for(int i=0;i<q;i++){ int l,r; cin>>l>>r; int sum=s[r]-s[l-1]; if(sum%3==0)puts("YES"); else puts("NO"); } return 0; } ``` Java ```java import java.util.*; public class Main { static int N = (int)1e5 + 10; static int[] s = new int[N]; static int f(int x) { //预处理数位之和 int res = 0; while (x > 0) { res += x % 10; x /= 10; } return res; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int q = scanner.nextInt(); for (int i = 1; i <= n; i++) { int x = scanner.nextInt(); s[i] = s[i - 1] + f(x); } for (int i = 0; i < q; i++) { int l = scanner.nextInt(); int r = scanner.nextInt(); int sum = s[r] - s[l - 1]; if (sum % 3 == 0) { System.out.println("YES"); } else { System.out.println("NO"); } } } } ``` Python ```python N = int(1e5) + 10 s = [0] * N def f(x): #预处理数位之和 res = 0 while x > 0: res += x % 10 x //= 10 return res n, q = map(int, input().split()) w=[0]+list(map(int,input().split())) for i in range(1, n + 1): s[i] = s[i - 1] + f(w[i]) for _ in range(q): l, r = map(int, input().split()) sum = s[r] - s[l - 1] if sum % 3 == 0: print("YES") else: print("NO") ``` [acwing 733. 构建回文](https://www.acwing.com/problem/content/735/) 难度系数：4 题解：一维前缀和+枚举技巧 首先，注意审题：题目明确说了，每一个方块都是一个大写字母， 本题的关键问题是如何快速判断某一个区间的所有字母，是否可以组成一个回文串 回文串，比如"aa"，"aabb"，"aba"，这些都是回文串，那么这些字符串的特点和共性是什么呢？ 题目说了，可以对方块进行重排，因此我们不需要考虑这些字母的顺序，我们来考虑这些字母的个数。 * 考虑一种极端情况：如果所有字母出现的次数都是偶数（0也是偶数），那一定是可以构成回文串的，例如上述的"aa"，"aabb" * 再考虑一种更一般的情况：除了某一个字母出现的次数是奇数，其他所有字母出现的个数都是偶数，这种情况也是可以构成回文串的，例如"aabaa" * 如果出现次数是奇数的字母个数$ge 2$，例如"aabcaa"，这种，是一定不能构成回文串的 因此，从上面三种情况我们可以得出一个结论：构成回文串的充要条件是区间内出现次数是奇数的字母个数$le 1$ 然后就是如何快速地去查询给定$[l,r]$区间内所有字母出现的次数，这里我们就可以使用一维前缀和的模版来计算，只不过由于字母有多个，因此需要使用二维数组来预处理前缀和。 我们定义$S[i][j]$表示区间$[1,i]$中字母 的出现次数，对应的递推方程（其实也可以称为状态转移方程，前缀和本质上就是一种动态规划）为： * 如果$s[i]=$，则有$S[i][j]=S[i-1][j]+ 1$ * 反之，则有$S[i][j]=S[i-1][j]$ 然后我们根据上述充要条件来判断即可。 C++ ```c++ #include<bits/stdc++.h> using namespace std; int T; void solve(int k){ //第k组测试数据的答案 int n,m; cin>>n>>m; string s; vector<vector<int>>S(n+1,vector<int>(26,0)); //定义前缀和数组 S[i][j]表示区间[1,i]中字母j的数量 cin>>s; for(int i=1;i<=n;i++){ //预处理前缀和 for(int j=0;j<26;j++){ S[i][j]=S[i-1][j]; if(j==s[i-1]-'A'){ S[i][j]++; } } } int res=0; //记录是回文串的个数 while(m--){ int l,r; cin>>l>>r; int num=0; //统计[l,r]区间内字母数量为奇数的个数 for(int i=0;i<26;i++){ //枚举[l,r]区间内26个字母的数量，并记录奇数字母的个数 int cnt=S[r][i]-S[l-1][i]; if(cnt%2==1)num++; } if(num<=1)res++; } printf("Case #%d: %d ",k,res); } int main(){ cin>>T; for(int i=1;i<=T;i++){ solve(i); } return 0; } ``` Java ```java import java.util.*; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int T = scanner.nextInt(); for (int k = 1; k <= T; k++) { int n = scanner.nextInt(); int m = scanner.nextInt(); String s = scanner.next(); int[][] S = new int[n + 1][26]; // 定义前缀和数组 S[i][j]表示区间[1,i]中字母j的数量 for (int i = 1; i <= n; i++) { // 预处理前缀和 for (int j = 0; j < 26; j++) { S[i][j] = S[i - 1][j]; if (j == s.charAt(i - 1) - 'A') { S[i][j]++; } } } int res = 0; // 记录是回文串的个数 while (m-- > 0) { int l = scanner.nextInt(); int r = scanner.nextInt(); int num = 0; // 统计[l,r]区间内字母数量为奇数的个数 for (int i = 0; i < 26; i++) { // 枚举[l,r]区间内26个字母的数量，并记录奇数字母的个数 int cnt = S[r][i] - S[l - 1][i]; if (cnt % 2 == 1) num++; } if (num <= 1) res++; } System.out.printf("Case #%d: %d ", k, res); } } } ``` Python ```python T = int(input()) for k in range(1, T + 1): n, m = map(int, input().split()) s = input() S = [[0] * 26 for _ in range(n + 1)] # 定义前缀和数组 S[i][j]表示区间[1,i]中字母j的数量 for i in range(1, n + 1): # 预处理前缀和 for j in range(26): S[i][j] = S[i - 1][j] if j == ord(s[i - 1]) - ord('A'): S[i][j] += 1 res = 0 # 记录是回文串的个数 for _ in range(m): l, r = map(int, input().split()) num = 0 # 统计[l,r]区间内字母数量为奇数的个数 for i in range(26): # 枚举[l,r]区间内26个字母的数量，并记录奇数字母的个数 cnt = S[r][i] - S[l - 1][i] if cnt % 2 == 1: num += 1 if num <= 1: res += 1 print(f"Case #{k}: {res}") ``` [最大加权矩形](http://121.196.235.151/p/P1016) 难度系数：4 题解：二维前缀和模板题 首先，我们可以使用二维前缀和的板子，来预处理出二维前缀和数组$S[i][j]$，$S[i][j]$表示以左上角$(1,1)$和点$(i,j)$构成的矩形内的元素权值和，预处理出二维前缀和数组之后，就可以在$O(1)$时间内计算出以$(x_1,y_1)$为矩形的左上角端点，$(x_2,y_2)$为矩形的右下角端点的矩形内的元素权值和。 然后本题需要我们找到权值和最大的矩形，因此我们可以按照以下这种方式来枚举所有的矩形 前两层循环分别枚举矩形的左上角端点$x_1,y_1$ 后面两层循环分别枚举矩形的右下角端点$x_2,y_2$ 整体的时间复杂度为$O(frac{n^4}{4})$ 其中，$nle 12$，因此$frac{n^4}{4}le frac{120^4}{4}=approx 5 imes 10^7)$ 是可以在1s内执行完的，虽然这波时间卡的有点极限，但凡$nle 200$都会超时。 当然，本题也有更加精妙的$O(n^3)$解法，需要利用到动态规划的相关知识，通过构建状态转移方程来优化时间复杂度，将会在动态规划专题中展开讲解。 C++ ```c++ #include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 130; int n; int a[N][N], s[N][N]; int main() { cin >> n; for (int i = 1; i <= n; i ++ ) //预处理二维前缀和 for (int j = 1; j <= n; j ++ ) cin >> a[i][j], s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + a[i][j]; int res=-1e9; for(int x1=1;x1<=n;x1++){ //枚举所有的子矩阵 for(int y1=1;y1<=n;y1++){ for(int x2=x1;x2<=n;x2++){ for(int y2=y1;y2<=n;y2++){ int sum=s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1]; res=max(res,sum); } } } } cout<<res<<endl; return 0; } ``` Java ```java import java.util.*; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int[][] a = new int[n + 1][n + 1]; int[][] s = new int[n + 1][n + 1]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { a[i][j] = scanner.nextInt(); s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + a[i][j]; // 预处理二维前缀和 } } int res = Integer.MIN_VALUE; for (int x1 = 1; x1 <= n; x1++) { // 枚举所有的子矩阵 for (int y1 = 1; y1 <= n; y1++) { for (int x2 = x1; x2 <= n; x2++) { for (int y2 = y1; y2 <= n; y2++) { int sum = s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1]; res = Math.max(res, sum); } } } } System.out.println(res); } } ``` Python（需要用pypy提交，并且卡了最后一个数据点） ```python n = int(input()) a = [[0] * (n + 2) for _ in range(n + 2)] s = [[0] * (n + 2) for _ in range(n + 2)] for i in range(1, n + 1): row = list(map(int, input().split())) for j in range(1, n + 1): a[i][j] = row[j - 1] s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + a[i][j] # 预处理二维前缀和 res = float('-inf') for x1 in range(1, n + 1): # 枚举所有的子矩阵 for y1 in range(1, n + 1): for x2 in range(x1, n + 1): for y2 in range(y1, n + 1): sum = s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1] res = max(res, sum) print(res) ``` [领地选择](http://121.196.235.151/p/P1017) 难度系数：4 题解：二维前缀和模板题 首先，我们可以使用二维前缀和的板子，来预处理出二维前缀和数组$S[i][j]$，$S[i][j]$表示以左上角$(1,1)$和点$(i,j)$构成的矩形内的元素权值和，预处理出二维前缀和数组之后，就可以在$O(1)$时间内计算出以$(x_1,y_1)$为矩形的左上角端点，$(x_2,y_2)$为矩形的右下角端点的矩形内的元素权值和。 本题要计算的是价值最高的正方形，且正方形的边长固定为 ，因此，我们可以直接枚举正方形的左上角端点$x_1,y_1$，然后根据边长 来计算出正方形的右下角端点$x_2,y_2$，利用二维前缀和计算公式即可在$O(1)$时间内计算出这个正方形的价值和。 时间复杂度：$O(n^2$ C++ ```c++ #include <iostream> using namespace std; const int N = 1010; int n, m, c; int a[N][N], s[N][N]; int main() { cin >> n >> m >> c; for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= m; j ++ ) { cin >> a[i][j]; s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + a[i][j]; // 预处理二维前缀和 } int res = -1e9, x = -1, y = -1; for (int x1 = 1; x1 <= n + 1 - c; x1 ++ ) // 枚举所有的子矩阵 for (int y1 = 1; y1 <=m + 1 - c; y1 ++ ) { int x2 = x1 + c - 1, y2 = y1 + c - 1; int total = s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1]; if (total > res) // 更新最大值，并更新矩形左上角坐标 { x = x1; y = y1; res = total; } } cout << x << " " << y << endl; return 0; } ``` Java（本题评测系统Java被卡内存，如果同时申请数组a和前缀和数组s，最后一个测试样例会报错：MLE） ```java import java.util.*; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int m = scanner.nextInt(); int c = scanner.nextInt(); int num; int[][] s = new int[n + 2][m + 2]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { num = scanner.nextInt(); s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + num; // 预处理二维前缀和 } } int res = Integer.MIN_VALUE; int x = -1, y = -1; for (int x1 = 1; x1 <= n + 1 - c; x1++) { // 枚举所有的子矩阵 for (int y1 = 1; y1 <= m + 1 - c; y1++) { int x2 = x1 + c - 1, y2 = y1 + c - 1; int total = s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1]; if (total > res) { // 更新最大值，并更新矩形左上角坐标 x = x1; y = y1; res = total; } } } System.out.println(x + " " + y); } } ``` Python ```python n,m,c=map(int,input().split()) a = [[0] * (n + 2) for _ in range(m + 2)] s = [[0] * (n + 2) for _ in range(m + 2)] for i in range(1, n + 1): row = list(map(int, input().split())) for j in range(1, m + 1): a[i][j] = row[j - 1] s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + a[i][j] # 预处理二维前缀和 res = float('-inf') x,y=-1,-1 for x1 in range(1, n + 2-c): # 枚举所有的子矩阵 for y1 in range(1, m + 2-c): x2,y2=x1+c-1,y1+c-1 total=s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1] if total>res: #更新最大值,并更新矩形左上角坐标 x,y=x1,y1 res=total print(x,y) ``` [完美矩形](http://121.196.235.151/p/P1006) 难度系数：4 题解：二维前缀和 $nle 20$，因此可以在$O(n^3$范围内求解 快速求一个矩形区域内的和：使用二维前缀和预处理 最终计算答案的时候，第一层循环枚举矩形长度$le$，第二，三层循环分别枚举矩形的左上角的端点$(x,y$ 对应右下角的端点则为$(x+len-1,y+len-1$ C++ ```c++ #include<bits/stdc++.h> using namespace std; const int N = 210; int n; char a[N][N]; int s[N][N]; int query(int x1,int y1,int x2,int y2){ return s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1]; } int main() { cin >> n; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ cin>>a[i][j]; } } for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= n; j ++ ) s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + (a[i][j]=='1'); for(int len=1;len<=n;len++){ int cnt=0; for(int x=1;x<=n-len+1;x++){ for(int y=1;y<=n-len+1;y++){ int sum=query(x,y,x+len-1,y+len-1); if(sum*2==len*len){ cnt++; } } } cout<<cnt<<endl; } return 0; } ``` Java ```java import java.util.Scanner; public class Main { static final int N = 210; static int n; static char[][] a = new char[N][N]; static int[][] s = new int[N][N]; static int query(int x1, int y1, int x2, int y2) { return s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1]; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); n = scanner.nextInt(); for (int i = 1; i <= n; i++) { String line = scanner.next(); for (int j = 1; j <= n; j++) { a[i][j] = line.charAt(j - 1); } } for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) { int value = a[i][j] == '1' ? 1 : 0; s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + value; } for (int len = 1; len <= n; len++) { int cnt = 0; for (int x = 1; x <= n - len + 1; x++) { for (int y = 1; y <= n - len + 1; y++) { int sum = query(x, y, x + len - 1, y + len - 1); if (sum * 2 == len * len) { cnt++; } } } System.out.println(cnt); } } } ``` Python ```python n = int(input()) a = [input() for _ in range(n)] s = [[0] * (n + 1) for _ in range(n + 1)] def query(x1, y1, x2, y2): return s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1] for i in range(1, n + 1): for j in range(1, n + 1): s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + (1 if a[i - 1][j - 1] == '1' else 0) for length in range(1, n + 1): cnt = 0 for x in range(1, n - length + 2): for y in range(1, n - length + 2): summation = query(x, y, x + length - 1, y + length - 1) if summation * 2 == length 2: cnt += 1 print(cnt) ``` [矩阵查询](http://121.196.235.151/p/P1007) 难度系数：5 题解：二维前缀和 首先我们注意，给定的字符串矩阵，只包含字符`x,y,z`，因此，对于每一个查询，我们其实就是要判断这个矩形中是否含有字符`x,y,z`。 我们可以定义一个三维前缀和数组$S[i][j][k$表示以$(1,1$为左上角，$(i,j$为右下角构成的矩形区域，含有字符`x,y,z`的个数，其中$k=$表示含有字符`x`的个数，$k=$表示含有字符`y`的个数，$k=$表示含有字符`z`的个数。 那么，对于给定的矩形区域，我们只需要查询对应的字符`x,y,z`的个数，即可得到答案。 然后我们需要将`x`映射到0，`y`映射到1，`z`映射到2，可以使用哈希表的`key-value`对来实现。 C++ ```c++ #include<bits/stdc++.h> using namespace std; const int N = 510; int n,m,q; int s[N][N][3]; char a[N][N]; int query(int x1,int y1,int x2,int y2,int k){ return s[x2][y2][k] - s[x2][y1 - 1][k] - s[x1 - 1][y2][k] + s[x1 - 1][y1 - 1][k]; } int main() { cin >> n>>m; unordered_map<char,int>mp={{'x',0},{'y',1},{'z',2}}; //构建字符串和下标的映射关系 for(int i=1;i<=n;i++){ //预处理二维前缀和 for(int j=1;j<=m;j++){ cin>>a[i][j]; int u=mp[a[i][j]]; for(int k=0;k<3;k++){ s[i][j][k] = s[i][j - 1][k] + s[i - 1][j][k] - s[i - 1][j - 1][k]; if(k==u)s[i][j][k]++; } } } cin>>q; while(q--){ int x1,y1,x2,y2; cin>>x1>>y1>>x2>>y2; int cnt=0; for(int i=0;i<3;i++){ //分别查询矩阵中是否含有字符x,y,z if(query(x1,y1,x2,y2,i)>0)cnt++; } cout<<cnt<<endl; } return 0; } ``` Java ```java import java.util.*; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int m = scanner.nextInt(); int[][][] a = new int[3][505][505]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { String x = scanner.next(); for (int k = 0; k < 3; k++) { a[k][i][j] = a[k][i - 1][j] + a[k][i][j - 1] - a[k][i - 1][j - 1]; // 二维前缀和转移 } if (x.equals("x")) { a[0][i][j]++; } else if (x.equals("y")) { a[1][i][j]++; } else { a[2][i][j]++; } } } int q = scanner.nextInt(); while (q-- > 0) { int x1 = scanner.nextInt(); int y1 = scanner.nextInt(); int x2 = scanner.nextInt(); int y2 = scanner.nextInt(); int res = 0; for (int i = 0; i < 3; i++) { // 查询 x, y, z 是否出现 res += get(a, i, x1, y1, x2, y2); } System.out.println(res); } } private static int get(int[][][] a, int id, int x1, int y1, int x2, int y2) { return a[id][x2][y2] - a[id][x1 - 1][y2] - a[id][x2][y1 - 1] + a[id][x1 - 1][y1 - 1] > 0 ? 1 : 0; // 只要id这个字符串它在子矩阵中出现至少一次，那就算一次答案。 } } ``` Python ```python n,m = map(int,input().split()) S = [[[0] * (m+1) for _ in range(n+1)] for _ in range(3)] matrix = [] mp = {0:'x',1:'y',2:'z'} # 构建字符串和下标的映射关系 for _ in range(n): row = input().split() matrix.append(row) q = int(input()) for idx in range(3): #预处理二维前缀和 for i in range(1,n+1): for j in range(1,m+1): S[idx][i][j] = S[idx][i-1][j] + S[idx][i][j-1] - S[idx][i-1][j-1] + (matrix[i-1][j-1] == mp[idx]) for _ in range(q): x1,y1,x2,y2 = map(int,input().split()) ans = 0 for idx in range(3): #分别查询矩阵中是否含有字符x,y,z if S[idx][x2][y2] - S[idx][x1-1][y2] - S[idx][x2][y1-1] + S[idx][x1-1][y1-1] > 0: ans += 1 print(ans) ``` 前缀和+哈希表 这一类题型，需要借助哈希表来存储相关数据，并结合前缀和来去求满足条件的子数组个数/子数组最大长度/子数组最小长度等，有趣的是，这一类题型中的部分题目，也可以使用双指针去求解，但是能用双指针求解的题目一般具有一个特点：子数组具有单调性，也就是数组中的元素不能含有负数。 以求满足条件的子数组个数这一问题举例，最暴力的做法，就是使用双重循环枚举出所有的子数组，然后逐一判断，对应的时间复杂度为$O(n^2$，而前缀和+哈希表这一算法，巧妙地利用了哈希表这种数据结构，并利用贡献法计数的思想来对问题进行求解，这里就不展开叙述，下面代入具体问题给大家分析。 [LeetCode 930. 和相同的二元子数组](https://leetcode.cn/problems/binary-subarrays-with-sum/description/) 难度系数：4 题解：前缀和+哈希表 这道题因为数组中的元素值都是非负数，因此具有单调性，可以使用双指针的方法来统计满足条件的子数组数量，但是，如果数组中的元素值有负数，就不可以使用双指针求解，因此，这里给出一个更加通用性的解法：前缀和+哈希表 对于所有的满足条件的方案数，我们分别考虑以下标 结尾的方案数，我们考虑它对结果的贡献，其实就是考虑以 结尾组成的子数组，有几个满足区间$[j,i]$满足：$区间和=goal$ 我们可以使用哈希表去统计$[0,i-1]$的前缀和的值以及其出现的次数，如果下标$j$满足条件，则一定能满足$s[i]-s[j]=goal$，$s[j]=s[i]-goal$，因此，我们只需要去查询哈希表中$key=s[i]-goal$对应的$val$值即可。由于只需要考虑$s[i]$，因此我们使用一个变量$s$代替前缀和数组即可。 对于示例1：`nums = [1,0,1,0,1]`, `goal = 2` 本题中，哈希表的`key-value`存的是前缀和及其出现次数 首先，我们考虑子数组为空的情况，此时的区间值为0，对应的方案数为1，也就是初始化哈希表$mp[0]=1$ 我们遍历到位置0，此时前缀和为1，为了使得区间和为2，我们需要找到另一个下标$j$，并且$j$对应的前缀和为-1，因此，就需要判断哈希表中是否存在`key`为-1的键值对，答案是不存在，因此没有以位置0结尾的满足题目条件的子数组。此时将$mp[1]+=1$,此时哈希表中$mp[0]=1,mp[1]=1$ 我们遍历到位置1，此时前缀和为1，为了使得区间和为2，我们需要找到另一个下标$j$，并且$j$对应的前缀和也为-1，因此，就需要判断哈希表中是否存在`key`为-1的键值对，答案是不存在，因此没有以位置1结尾的满足题目条件的子数组。此时将$pos[1]+=1$，此时哈希表中$mp[0]=1,mp[1]=2$ 我们遍历到位置2，此时前缀和为2，为了使得区间和为2，我们需要找到另一个下标$j$，并且$j$对应的前缀和为0，因此，就需要判断哈希表中是否存在`key`为0的键值对，答案是存在$mp[0]=1$，因此将方案数$res$累加上$mp[0]$的值，即$res+=mp[0]$，以位置2结尾的满足题目条件的子数组的个数为1，对应的子数组为【1,0,1】，并将$pos[2]+=1$，此时哈希表中$mp[0]=1,mp[1]=2,mp[2]=1$ 我们遍历到位置3，此时前缀和为2，为了使得区间和为2，我们需要找到另一个下标$j$，并且$j$对应的前缀和为0，因此，就需要判断哈希表中是否存在`key`为0的键值对，答案是存在$mp[0]=$，因此将方案数$res$累加上$mp[0]$的值，即$res+=mp[0]$，以位置3结尾的满足题目条件的子数组的个数为1，对应的子数组为【1,0,1,0】，并将$pos[2]+=$，此时哈希表中$mp[0]=1,mp[1]=2,mp[2]=2$ 我们遍历到位置4，此时前缀和为3，为了使得区间和为2，我们需要找到另一个下标$j$，并且$j$对应的前缀和为1，因此，就需要判断哈希表中是否存在`key`为1的键值对，答案是存在$mp[1]=2$，因此将方案数$res$累加上$mp[1]$的值，即$res+=mp[1]$，以位置4结尾的满足题目条件的子数组的个数为1，对应的子数组为【0,1,0，1】、【1,0,1】，并将$pos[3]+=1$，此时哈希表中$mp[0]=1,mp[1]=2,mp[2]=2,mp[3]=1$ 具体可以参考下面视频 C++ ```c++ class Solution { public: int numSubarraysWithSum(vector<int>& nums, int goal) { int res = 0, n = nums.size(); unordered_map<int, int> mp; mp[0] = 1; // 初始化前缀和为0的情况，出现一次 int sum = 0; for (int i = 0; i < n; i++) { sum += nums[i]; // 计算当前位置的前缀和 // 如果前缀和为 s - goal 的情况已经出现过，累加到结果中 res += mp[sum - goal]; // 更新前缀和的出现次数 mp[sum]++; } return res; } }; ``` Java ```java import java.util.HashMap; import java.util.Map; class Solution { public int numSubarraysWithSum(int[] nums, int goal) { int res = 0, n = nums.length; Map<Integer, Integer> map = new HashMap<>(); map.put(0, 1); // 初始化前缀和为0的情况，出现一次 for (int i = 0, sum = 0; i < n; i++) { sum += nums[i]; // 计算当前位置的前缀和 // 如果前缀和为 sum - goal 的情况已经出现过，累加到结果中 res += map.getOrDefault(sum - goal, 0); // 更新前缀和的出现次数 map.put(sum, map.getOrDefault(sum, 0) + 1); } return res; } } ``` Python ```python class Solution: def numSubarraysWithSum(self, nums, goal): res, n = 0, len(nums) prefix_sum = defaultdict(int) # 使用 defaultdict 初始化前缀和字典 prefix_sum[0] = 1 # 初始化前缀和为 0 的情况，出现一次 s = 0 for num in nums: s += num # 计算当前位置的前缀和 # 如果前缀和为 s - goal 的情况已经出现过，累加到结果中 res += prefix_sum[s - goal] # 更新前缀和的出现次数 prefix_sum[s] += 1 return res ``` [acwing 1230. K倍区间](https://www.acwing.com/problem/content/description/1232/) 难度系数：5 题解：前缀和+哈希表+取模 本题和上面的LeetCode 930很像，唯一的区别在于，需要计算的是 的倍数的区间，因此，我们可以考虑重新定义前缀和$su$，我们定义$su$为区间$[1,i$中的区间和对$K$取模后的结果，并且哈希表中存的所有前缀和也都是对 取模后的结果，这样，我们一遍遍历，一遍考虑以 结尾的区间的方案数，就可以直接计算哈希表中`key`为$su$的元素个数即可，由于是求方案数，因此同样需要初始化哈希表$mp[0]=$ 本题C++和Java选手需要注意：方案数可能很大，会爆int，因此需要使用`long long`来存储最终的方案数。 极限方案数：每一个子数组都是一个合法方案，对应的方案数为$frac{n imes (n+1)}{2}$，其中$nle 10^5$，因此最终结果约为$5 imes 10^9>2^{31}-1$，会爆int。 C++ ```c++ #include<bits/stdc++.h> using namespace std; int main(){ int n, k; cin >> n >> k; vector<int> a(n + 1); for (int i = 1; i <= n; i++) { cin >> a[i]; } unordered_map<int, int> mp; mp[0] = 1; // 哈希表初始化 long long res = 0; // 方案数 int total = 0; // 区间和%k的值 for (int i = 1; i <= n; i++) { // 枚举以i结尾的方案数 total = (total + a[i]) % k; if (mp.count(total)) { res += mp[total]; } mp[total]++; // 更新哈希表 } cout << res << endl; return 0; } ``` Java ```java import java.util.*; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int k = scanner.nextInt(); int[] a = new int[n + 1]; for (int i = 1; i <= n; i++) { a[i] = scanner.nextInt(); } Map<Integer, Integer> mp = new HashMap<>(); mp.put(0, 1); // 哈希表初始化 int res = 0; // 方案数 int total = 0; // 区间和%k的值 for (int i = 1; i <= n; i++) { // 枚举以i结尾的方案数 total = (total + a[i]) % k; if (mp.containsKey(total)) { res += mp.get(total); } mp.put(total, mp.getOrDefault(total, 0) + 1); // 更新哈希表 } System.out.println(res); } } ``` Python ```python n,k=map(int,input().split()) a=[0] for _ in range(n): a.append(int(input())) mp={0:1} #哈希表初始化 res=0 #方案数 total=0 #区间和%k的值 for i in range(1,n+1): #枚举以i结尾的方案数 total=(total+a[i])%k if total in mp: res+=mp[total] mp[total]=mp.get(total,0)+1 #更新哈希表 print(res) ``` [魔法师](http://121.196.235.151/p/P1009) 难度系数：6 题解：前缀和+哈希表+位运算 首先，注意到本题中数组的每个元素都是一个非0整数，也就是说，任意一个区间内所有元素的乘积，不是正数就是负数，对于一个长度为 的数组，它的子数组的个数为：区间长度为1的数组的个数+区间长度为2的数组的个数+...+区间长度为 的数组的个数=$n+(n-1)+...+1=frac{(n imes (n+1))}{2}$ 也就是说，我们只需要计算区间内所有元素乘积为正数的数量 ，就可以根据子数组的总数量减去 得到区间内所有元素乘积为负数的数量。 对于区间内所有元素乘积为正数的区间，有这样一个特点：区间内的负数个数一定是偶数，如0个，2个，4个，...，$2$个。 也就是说，我们需要去考虑所有子数组区间的奇偶性（这里指的是区间内的负数个数的奇偶性） 对于子数组区间的奇偶性，不是奇数，就是偶数，因此是符合一个二进制数的（不是0就是1） 因此，我们可以利用前缀和+哈希表的思想来统计以 结尾的子数组中区间内负数个数为偶数的方案数。 设前缀和$s[i]$为区间$[1,i]$的负数个数，对于以$i$结尾的方案数而言，如果$[j,i]$区间满足区间内负数的个数为偶数，则说明$s[j-1]$与$s[i]$所对应的奇偶性相同。 前面我们都是利用加法来进行运算，但是这里只有两种情况：0和1，因此我们可以使用不进位的加法运算符：异或来实现优化（当然如果你不想使用异或运算符，可以参考acwing 1230的思路），将前缀和对2取模即可，下面给出两种解法的AC代码。 C++(不使用异或运算） ```c++ #include<bits/stdc++.h> using namespace std; const int N=2E5+10; int a[N],n; int main(){ cin>>n; for(int i=1;i<=n;i++){ //将a[i]表示为第i个数字是否为负数(a[i]=1说明第i个数是负数) cin>>a[i]; if(a[i]>0)a[i]=0; else a[i]=1; } long long total=1ll*n*(n+1)/2; //总的子数组个数 unordered_map<int,int>cnts; //记录前缀和区间的负数个数的奇偶性 cnts[0]=1; //初始没有任何数，可以视为有0个负数，因此cnts[0]=1 long long white=0; //统计子数组内负数个数为偶数的区间数 for(int i=1,s=0;i<=n;i++){ s=(s+a[i])%2; if(cnts.count(s)){ white+=cnts[s]; } cnts[s]++; } cout<<total-white<<" "<<white<<endl; return 0; } ``` C++(使用异或运算) ```c++ #include<bits/stdc++.h> using namespace std; const int N=2E5+10; int a[N],n; int main(){ cin>>n; for(int i=1;i<=n;i++){ //将a[i]表示为第i个数字是否为负数(a[i]=1说明第i个数是负数) cin>>a[i]; if(a[i]>0)a[i]=0; else a[i]=1; } long long total=1ll*n*(n+1)/2; //总的子数组个数 unordered_map<int,int>cnts; //记录前缀和区间的负数个数的奇偶性 cnts[0]=1; //初始没有任何数，可以视为有0个负数，因此cnts[0]=1 long long white=0; //统计子数组内负数个数为偶数的区间数 for(int i=1,s=0;i<=n;i++){ s^=a[i]; if(cnts.count(s)){ white+=cnts[s]; } cnts[s]++; } cout<<total-white<<" "<<white<<endl; return 0; } ``` Java(不使用异或运算） ```java import java.util.*; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int[] a = new int[n + 1]; for (int i = 1; i <= n; i++) { // 将a[i]表示为第i个数字是否为负数(a[i]=1说明第i个数是负数) a[i] = scanner.nextInt(); if (a[i] > 0) a[i] = 0; else a[i] = 1; } long total = 1L * n * (n + 1) / 2; // 总的子数组个数 Map<Integer, Integer> cnts = new HashMap<>(); // 记录前缀和区间的负数个数的奇偶性 cnts.put(0, 1); // 初始没有任何数，可以视为有0个负数，因此cnts[0]=1 long white = 0; // 统计子数组内负数个数为偶数的区间数 for (int i = 1, s = 0; i <= n; i++) { s = (s + a[i]) % 2; if (cnts.containsKey(s)) { white += cnts.get(s); } cnts.put(s, cnts.getOrDefault(s, 0) + 1); } System.out.println((total - white) + " " + white); } } ``` Java(使用异或运算) ```java import java.util.*; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int[] a = new int[n + 1]; for (int i = 1; i <= n; i++) { // 将a[i]表示为第i个数字是否为负数(a[i]=1说明第i个数是负数) a[i] = scanner.nextInt(); if (a[i] > 0) a[i] = 0; else a[i] = 1; } long total = 1L * n * (n + 1) / 2; // 总的子数组个数 Map<Integer, Integer> cnts = new HashMap<>(); // 记录前缀和区间的负数个数的奇偶性 cnts.put(0, 1); // 初始没有任何数，可以视为有0个负数，因此cnts[0]=1 long white = 0; // 统计子数组内负数个数为偶数的区间数 for (int i = 1, s = 0; i <= n; i++) { s^=a[i]; if (cnts.containsKey(s)) { white += cnts.get(s); } cnts.put(s, cnts.getOrDefault(s, 0) + 1); } System.out.println((total - white) + " " + white); } } ``` Python(不使用异或运算） ```python n = int(input()) a=[0]+list(map(int,input().split())) for i in range(1, n + 1): # 将a[i]表示为第i个数字是否为负数(a[i]=1说明第i个数是负数) if a[i] > 0: a[i] = 0 else: a[i] = 1 total = n * (n + 1) // 2 # 总的子数组个数 cnts = {0: 1} # 记录前缀和区间的负数个数的奇偶性 white = 0 # 统计子数组内负数个数为偶数的区间数 s = 0 for i in range(1, n + 1): s = (s + a[i]) % 2 if s in cnts: white += cnts[s] cnts[s] = cnts.get(s, 0) + 1 print(total - white, white) ``` Python(使用异或运算) ```python n = int(input()) a=[0]+list(map(int,input().split())) for i in range(1, n + 1): # 将a[i]表示为第i个数字是否为负数(a[i]=1说明第i个数是负数) if a[i] > 0: a[i] = 0 else: a[i] = 1 total = n * (n + 1) // 2 # 总的子数组个数 cnts = {0: 1} # 记录前缀和区间的负数个数的奇偶性 white = 0 # 统计子数组内负数个数为偶数的区间数 s = 0 for i in range(1, n + 1): s^=a[i] if s in cnts: white += cnts[s] cnts[s] = cnts.get(s, 0) + 1 print(total - white, white) ``` [acwing 3553. 最长平衡串](https://www.acwing.com/problem/content/description/3556/) 难度系数：4 题解：前缀和+哈希表 注意，本题求的是子串，是连续的一段字符串。 我们把字符`'0'`看成数值1，字符`'1'`看成数值-1，那么问题就变为：求一段最长的区间，使得其满足区间和为0 那么，我们参考上面的前缀和+哈希表的思路，求方案数，我们是考虑以下标 结尾的方案数，求最长的区间，那么我们就考虑以下标 结尾的最长区间，当然，也可能不存在以 结尾的最长区间，例如字符串：`'1111'`，以任意一个下标结尾的满足题目条件的最长区间均为0。 本题中，哈希表的`key-value`存的不是前缀和及其出现次数，而是前缀和及其下标（所有求最大/最小长度的题目哈希表的`value`存的都是下标值） 以题目给的样例：为例 首先，我们考虑字符串为空的情况，此时的区间值为0，对应的下标应为-1，也就是初始化哈希表$pos[0]=-1$，这里取-1是因为字符串下标从0开始。 我们遍历到位置0，此时前缀和为-1，为了使得区间和为0，我们需要找到另一个下标$j$，并且$j$对应的前缀和也为-1，因此，就需要判断哈希表中是否存在`key`为-1的键值对，答案是不存在，因此没有以位置0结尾的满足题目条件的子串。此时将$pos[-1]=0$添加到哈希表中 我们遍历到位置1，此时前缀和为0，为了使得区间和为0，我们需要找到另一个下标$j$，并且$j$对应的前缀和也为0，因此，就需要判断哈希表中是否存在`key`为0的键值对，答案是存在$pos[0]=-$，因此我们更新最大长度$res=max(res,i-pos[0])=max(res,2)$,$res$更新为2。对应的字符串为"10" 我们遍历到位置2，此时前缀和为-1，为了使得区间和为0，我们需要找到另一个下标$j$，并且$j$对应的前缀和也为-1，因此，就需要判断哈希表中是否存在`key`为-1的键值对，答案是存在$pos[-1]=0$，因此我们更新最大长度$res=max(res,i-pos[-1])=max(res,2)$,$res$仍为2。对应的字符串为"01" 我们遍历到位置3，此时前缀和为0，为了使得区间和为0，我们需要找到另一个下标$j$，并且$j$对应的前缀和也为0，因此，就需要判断哈希表中是否存在`key`为0的键值对，答案是存在$pos[0]=-1$，因此我们更新最大长度$res=max(res,i-pos[0])=max(res,4)$,$res$更新为4。对应的字符串为"1010" 我们遍历到位置4，此时前缀和为-1，为了使得区间和为0，我们需要找到另一个下标$j$，并且$j$对应的前缀和也为-1，因此，就需要判断哈希表中是否存在`key`为-1的键值对，答案是存在$pos[-1]=0$，因此我们更新最大长度$res=max(res,i-pos[-1])=max(res,4)$,$ress$值仍为4。对应的字符串为"0101" 我们遍历到位置5，此时前缀和为-2，为了使得区间和为0，我们需要找到另一个下标$j$，并且$j$对应的前缀和也为-2，因此，就需要判断哈希表中是否存在`key`为-1的键值对，答案是不存在，因此没有以位置5结尾的满足题目条件的子串。此时将$pos[-2]=5$添加到哈希表中 我们遍历到位置6，此时前缀和为-1，为了使得区间和为0，我们需要找到另一个下标$j$$j$并且 对应的前缀和也为-1，因此，就需要判断哈希表中是否存在`key`为-1的键值对，答案是存在$pos[-1]=0$，因此我们更新最大长度$res=max(res,i-pos[-1])=max(res,6)$,$res$更新为6。对应的字符串为"010110" 我们遍历到位置7，此时前缀和为0，为了使得区间和为0，我们需要找到另一个下标$j$，$j$并且 对应的前缀和也为0，因此，就需要判断哈希表中是否存在`key`为0的键值对，答案是存在$pos[0]=-1$，因此我们更新最大长度$res=max(res,i-pos[0])=max(res,8)$,$res$更新为8。对应的字符串为"" 我们遍历到位置8，此时前缀和为1，为了使得区间和为0，我们需要找到另一个下标 ，并且 对应的前缀和也为1，因此，就需要判断哈希表中是否存在`key`为1的键值对，答案是不存在，因此没有以位置8结尾的满足题目条件的子串。此时将$pos[1]=8$添加到哈希表中 具体可以参考下面视频 C++ ```c++ #include<bits/stdc++.h> using namespace std; int main(){ string s; cin>>s; int n=s.size(),res=0; unordered_map<int,int>pos; pos[0]=-1; //哈希表初始化，表示空串的情况 for(int i=0,sum=0;i<n;i++){ if(s[i]=='0')sum++; //更新前缀和 else sum--; if(pos.count(sum)){ //如果存在对应子串 res=max(res,i-pos[sum]); //更新最大长度 } else{ //不存在子串，更新哈希表 pos[sum]=i; } } cout<<res<<endl; return 0; } ``` Java ```java import java.util.*; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String s = scanner.nextLine(); int n = s.length(), res = 0; Map<Integer, Integer> pos = new HashMap<>(); pos.put(0, -1); // 哈希表初始化，表示空串的情况 for (int i = 0, sum = 0; i < n; i++) { if (s.charAt(i) == '0') sum++; // 更新前缀和 else sum--; if (pos.containsKey(sum)) { // 如果存在对应子串 res = Math.max(res, i - pos.get(sum)); // 更新最大长度 } else { // 不存在子串，更新哈希表 pos.put(sum, i); } } System.out.println(res); } } ``` Python ```python s = input() n = len(s) res = 0 pos = {0: -1} # 哈希表初始化，表示空串的情况 sum = 0 for i in range(n): if s[i] == '0': sum += 1 # 更新前缀和 else: sum -= 1 if sum in pos: # 如果存在对应子串 res = max(res, i - pos[sum]) # 更新最大长度 else: # 不存在子串，更新哈希表 pos[sum] = i print(res) ``` [最长平均数](http://121.196.235.151/p/P1008) 难度系数：6 题解：数学推导+前缀和+哈希表 下标从`1`开始，使用前缀和计算区间`[1,i]`的区间和`s[i]`，对于以`i`结尾的区间，如果存在满足条件的区间`[j,i]`，使得区间的平均数为`k`，我们定义区间的长度为$len$,则有 $s[i]-s[j-1]=k*len,其中len=i-j+1$ 则有$s[i]-s[j-1]=k*(i-j+1)$ 把`j`和`i`移到同一边，则有：$s[i]-k*i=s[j-1]-(j-1)*k$ 因此，当枚举到 时，只需要判断哈希表中是否存在$s[i]-k*i$即可，如果存在，则更新最大长度，不存在的话，就把当前的值（$s[i]-k*i$）和下标($i$)作为哈希表的$key$和$val$存到哈希表中 举个例子，比如数组为$a=[4,3,2,5],k=3$，这里的数组下标从1开始，方便前缀和计算 一开始初始化哈希表为$mp[s[0]-0*k]=mp[0-0]=mp[0]=0$ 遍历到下标1，就是元素4的位置，计算数值$s[1]-1*k=4-3=1$，哈希表中不存在1，记录$mp[1]=1$后，跳过 遍历到下标2，就是元素3的位置，计算数值$s[2]-2*k=4+3-2*3=1$，哈希表中存在1，更新最大长度$res=max(res,i-mp[s[i]-k*i])=max(res,2-1)=1$，也就是子数组【3】，找到了一个答案 遍历到下标3，计算数值$s[3]-3*k=4+3+2-3*3=0$ 哈希表中存在1，更新最大长度$res=max(res,i-mp[s[i]-k*i])=max(res,3-0)=3$ ，也就是子数组【4，3，2】，找到全局最优解 遍历到下标4，计算数值$s[4]-4*k=4+3+2+5-4*3=2$，哈希表中不存在2，记录$mp[2]=4$后，跳过 具体可以参考下面视频 C++ ```c++ #include <bits/stdc++.h> using namespace std; const int N=1E5+10; long long T,w[N],n,k; int res=-1; int main(){ cin>>n>>k; for(int i=1;i<=n;i++)cin>>w[i]; map<long long,int>mp; mp[0]=0; long long sum=0; for(int i=1;i<=n;i++){ sum+=w[i]; if(mp.count(sum-k*i)){ res=max(res,i-mp[sum-k*i]); //更新最大长度 } else{ mp[sum-k*i]=i; } } cout<<res<<endl; return 0; } ``` Java ```java import java.util.HashMap; import java.util.Map; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); long k = scanner.nextLong(); long[] w = new long[n + 1]; for (int i = 1; i <= n; i++) { w[i] = scanner.nextLong(); } Map<Long, Integer> mp = new HashMap<>(); mp.put(0L, 0); long sum = 0; int res = -1; for (int i = 1; i <= n; i++) { sum += w[i]; if (mp.containsKey(sum - k * i)) { res = Math.max(res, i - mp.get(sum - k * i)); } else { mp.put(sum - k * i, i); } } System.out.println(res); } } ``` Python3 ```python n, k = map(int, input().split()) w = [0] + list(map(int, input().split())) mp = {0: 0} res = -1 s = 0 for i in range(1, n + 1): s += w[i] if s - k * i in mp: res = max(res, i - mp[s - k * i]) else: mp[s - k * i] = i print(res) ``` 前后缀分解 这一类题型，一般都是会把整个区间拆成两个部分或者三个部分 从前往后遍历 后半部分的信息用一个预处理的后缀和数组维护（维护区间`[i,n]`的信息） 前半部分的信息直接通过遍历处理得到 然后根据策略去计算目标值（可能会用到乘法原理，组合数学等数学知识） 算法本质：其实还是一个动态规划的思想，能使用前后缀分解来处理的题目，大多也都可以使用动态规划（一般是状态机 DP）来求解，不过前后缀分解有时候学明白了的话要比动态规划更容易写出来。 这类题型没有太多固定的模版，大家做个2-3题，就会有一定感觉了，在做的过程中积累即可。 [LeetCode 238. 除自身以外数组的乘积](https://leetcode.cn/problems/product-of-array-except-self/description/) 难度系数：4 题解：前后缀分解 首先观察数据范围，$nle 10^5$，因此我们必须设计一个$O(n)$或者$O(nlogn)$的算法来求解，否则会超时。 首先，我们考虑暴力做法：对于每一个下标 ，分别去枚举计算区间$[0,i-1]$的元素乘积和区间$[i+1,n-1]$的元素乘积，这样对应的时间复杂度为$O(n^2)$，会超时。 更加高效的做法：我们可以把每一个位置 左侧和右侧的元素乘积，分别用 和 数组去保存下来，这样在遍历的时候，我们就可以利用$l[i-1] imes r[i+1]$在$O(1)$的时间内得到位置 的乘积之和。这样总的时间复杂度就从$O(n^2)$降低至$O(n)$ 那么，参考前缀和的递推公式，我们可以得出$l[i],r[i]$的地推公式（本质上来说其实是动态规划） * $l[i]=l[i-1] imes nums[i-1]$ * $r[i]=r[i+1] imes nums[i+1]$ 需要初始化$l[0]=r[n-1]=1$ 当然，如果熟练的小伙伴，可以只预处理右侧的数组 ，左侧的数组 可以一边枚举一边计算。 C++ ```c++ class Solution { public: vector<int> productExceptSelf(vector<int>& nums) { int n=nums.size(); vector<int>res(n),r(n,1),l(n,1); for(int i=1;i<n;i++){ //预处理l[i],表示i左侧的所有元素的乘积 l[i]=l[i-1]*nums[i-1]; } for(int i=n-2;i>=0;i--){ //预处理r[i],表示i右侧的所有元素的乘积 r[i]=r[i+1]*nums[i+1]; } for(int i=0;i<n;i++){ //枚举计算每一个位置的乘积之和（左边*右边） int left=1,right=1; if(i>0)left=l[i]; if(i+1<n)right=r[i]; res[i]=left*right; } return res; } }; ``` Java ```java public class Solution { public int[] productExceptSelf(int[] nums) { int n = nums.length; int[] res = new int[n]; int[] r = new int[n]; int[] l = new int[n]; Arrays.fill(r, 1); Arrays.fill(l, 1); for (int i = 1; i < n; i++) { // 预处理l[i],表示i左侧的所有元素的乘积 l[i] = l[i - 1] * nums[i - 1]; } for (int i = n - 2; i >= 0; i--) { // 预处理r[i],表示i右侧的所有元素的乘积 r[i] = r[i + 1] * nums[i + 1]; } for (int i = 0; i < n; i++) { // 枚举计算每一个位置的乘积之和（左边*右边） int left = 1, right = 1; if (i > 0) left = l[i]; if (i + 1 < n) right = r[i]; res[i] = left * right; } return res; } } ``` Python ```python class Solution: def productExceptSelf(self, nums): n = len(nums) res, r, l = [0]*n, [1]*n, [1]*n for i in range(1, n): # 预处理l[i],表示i左侧的所有元素的乘积 l[i] = l[i - 1] * nums[i - 1] for i in range(n - 2, -1, -1): # 预处理r[i],表示i右侧的所有元素的乘积 r[i] = r[i + 1] * nums[i + 1] for i in range(n): # 枚举计算每一个位置的乘积之和（左边*右边） left = 1 if i == 0 else l[i] right = 1 if i == n - 1 else r[i] res[i] = left * right return res ``` [LeetCode 2909. 元素和最小的山形三元组 II](https://leetcode.cn/problems/minimum-sum-of-mountain-triplets-ii/description/) 难度系数：5 题解：前后缀分解 对于这种三元组的问题，大家看到了第一反应就应该是要枚举中间元素来求解！大部分题目都是可以通过这种方式来优化时间复杂度的！！ 我们可以枚举中间元素$j$，那么对于中间元素$j$，它构成的最小元素和的答案一定是左边比它小的最小的元素值与右边比它小的最小的元素值构成的三元组。 我们可以使用两个数组$l$和$r$ ，$l[i]$表示$i$左边元素的最小值，$r[i]$表示$i$右边元素的最小值，那么如果有$l[i],r[i]le nums[i]$，就可以更新最小值为$res=min(res,l[i]+r[i]+nums[i])$ $l[i],r[i]$的地推公式我们可以得出有 * $l[i]=min(l[i-1],nums[i-1])$ * $r[i]=min(r[i+1],nums[i+1])$ 由于求的是最小值，因此我们可以将其初始化为$l[0]=10^9,r[n-1]=10^9$ C++ ```c++ class Solution { public: int minimumSum(vector<int>& nums) { int n = nums.size(); vector<int>l(n,1e9),r(n,1e9); int res=1e9; //求最小值，初始化为一个较大的数 for(int i=1;i<n;i++){ //预处理l[i],表示i左侧元素的最小值 l[i]=min(l[i-1],nums[i-1]); } for(int i=n-2;i>=0;i--){ //预处理r[i],表示i右侧元素的最小值 r[i]=min(r[i+1],nums[i+1]); } for(int j=1;j<n-1;j++){ //枚举三元组(i,j,k)中的j if(l[j]<nums[j]&&r[j]<nums[j]){ res=min(res,l[j]+nums[j]+r[j]); } } return (res==1e9)?-1:res; } }; ``` Java ```java import java.util.*; public class Solution { public int minimumSum(int[] nums) { int n = nums.length; int[] l = new int[n]; int[] r = new int[n]; Arrays.fill(l, Integer.MAX_VALUE); Arrays.fill(r, Integer.MAX_VALUE); int res = Integer.MAX_VALUE; // 求最小值，初始化为一个较大的数 for (int i = 1; i < n; i++) { // 预处理l[i],表示i左侧元素的最小值 l[i] = Math.min(l[i - 1], nums[i - 1]); } for (int i = n - 2; i >= 0; i--) { // 预处理r[i],表示i右侧元素的最小值 r[i] = Math.min(r[i + 1], nums[i + 1]); } for (int j = 1; j < n - 1; j++) { // 枚举三元组(i,j,k)中的j if (l[j] < nums[j] && r[j] < nums[j]) { res = Math.min(res, l[j] + nums[j] + r[j]); } } return (res == Integer.MAX_VALUE) ? -1 : res; } } ``` Python ```python class Solution: def minimumSum(self, nums): n = len(nums) l, r = [float('inf')] * n, [float('inf')] * n res = float('inf') # 求最小值，初始化为一个较大的数 for i in range(1, n): # 预处理l[i],表示i左侧元素的最小值 l[i] = min(l[i - 1], nums[i - 1]) for i in range(n - 2, -1, -1): # 预处理r[i],表示i右侧元素的最小值 r[i] = min(r[i + 1], nums[i + 1]) for j in range(1, n - 1): # 枚举三元组(i,j,k)中的j if l[j] < nums[j] and r[j] < nums[j]: res = min(res, l[j] + nums[j] + r[j]) return -1 if res == float('inf') else res ``` [acwing 4977. 三元组](https://www.acwing.com/problem/content/description/4980/) 难度系数：5 题解：前后缀分解+枚举技巧 又是一个三元组问题，参考上面LeetCode 2909的思路，显然我们应该去枚举中间值 来求解 比如枚举到位置 ，对应的元素值为$w[i]$，我们可以统计$i$左侧的所有满足$w[j] imes k=w[i]$的 ，以及 右侧的所有满足$w[i] imes k =w[j]$的&#x20; 其实就是枚举 左侧的$frac{w[i]}{k}$的个数，以及 右侧的$w[i] imes l$的个数（当然前提必须要$w[i]$是$i$的倍数） 考虑到这里，我们就可以使用之前的思路，分别使用两个哈希表$l,r$来维护每一个位置 左侧的$frac{w[i]}{k}$的个数，以及$i$右侧的$w[i] imes k$的个数 这样，我们根据乘法原理，对于位置 的方案数就是$l[frac{w[i]}{k}] imes r[w[i]] imes k$ 由于我们需要考虑的是对应元素出现的次数，因此需要使用哈希表这种数据结构来存储，并且需要对维护左侧和右侧元素个数的哈希表进行预处理操作，保证枚举到位置 时（下标从0开始），左侧哈希表存储的是区间$[0,i-1]$中每个元素的出现次数，右侧哈希表存储的是区间$[i+1,n-1]$中每个元素出现的次数。 本题注意细节：数据范围较大，对于C++和Java选手，需要使用`long long`来存储。 C++ ```c++ #include<bits/stdc++.h> using namespace std; const int N=2E5+10; int n,w[N],k; int main(){ cin>>n>>k; for(int i=0;i<n;i++)cin>>w[i]; unordered_map<long long,int>mp1; //记录每个元素出现的次数 for(int i=1;i<n;i++){ //记录区间[2,n-1]中每个元素出现的次数 mp1[w[i]]++; } unordered_map<long long,int>mp2; //记录区间[0,i-1]中每个元素出现的次数 mp2[w[0]]++; long long res=0; for(int i=1;i<n-1;i++){ //枚举y mp1[w[i]]--; if(w[i]%k){ //如果不是k的整数倍 直接枚举下一个元素 mp2[w[i]]++; continue; } if(mp1.count(1ll*w[i]*k)&&mp2.count(w[i]/k)){ res+=1ll*mp1[w[i]*k]*mp2[w[i]/k]; } mp2[w[i]]++; } cout<<res<<endl; return 0; } ``` Java ```java import java.util.*; public class Main{ public static void main(String[] args){ Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); // 读入数组长度 int k = scanner.nextInt(); // 读入k值 long[] a = new long[n]; // 定义数组a Map<Long, Integer> map1 = new HashMap<>(); // 记录区间[2,n-1]中每个元素出现的次数 Map<Long, Integer> map2 = new HashMap<>(); // 记录区间[0,i-1]中每个元素出现的次数 for(int i = 0; i < n; i++){ // 遍历数组 a[i] = scanner.nextLong(); // 读入数组元素 map2.put(a[i], map2.getOrDefault(a[i], 0) + 1); // 更新map2中元素的出现次数 } long res = 0; // 结果变量 for(int i = 0; i < n; i++){ // 枚举y long ay = a[i]; // 取出当前元素 map2.put(ay, map2.get(ay) - 1); // 将当前元素在map2中的出现次数减1 if(ay % k == 0){ // 如果是k的整数倍 long ax = ay / k; // 计算ax long az = ay * k; // 计算az res += (long)map1.getOrDefault(ax, 0) * map2.getOrDefault(az, 0); // 更新结果 } map1.put(ay, map1.getOrDefault(ay, 0) + 1); // 更新map1中元素的出现次数 } System.out.println(res); // 输出结果 } } ``` Python3 ```python n, k = map(int, input().split()) # 读入数组长度和k值 w = list(map(int, input().split())) # 读入数组元素 mp1 = {} # 记录区间[2,n-1]中每个元素出现的次数 mp2 = {w[0]: 1} # 记录区间[0,i-1]中每个元素出现的次数 res = 0 # 结果变量 for i in range(1, n): # 记录区间[2,n-1]中每个元素出现的次数 mp1[w[i]] = mp1.get(w[i], 0) + 1 for i in range(1, n - 1): # 枚举y mp1[w[i]] -= 1 if w[i] % k != 0: # 如果不是k的整数倍 直接枚举下一个元素 mp2[w[i]] = mp2.get(w[i], 0) + 1 continue if mp1.get(w[i] * k, 0) and mp2.get(w[i] // k, 0): # 如果w[i]*k和w[i]//k都存在 res += mp1[w[i] * k] * mp2[w[i] // k] # 更新结果 mp2[w[i]] = mp2.get(w[i], 0) + 1 print(res) # 输出结果 ``` [acwing 4114. 垃圾桶](https://www.acwing.com/problem/content/description/4117/) 难度系数：5 题解：前后缀分解 首先观察数据范围，哪怕只是读取输入，都有$O(TN)$的复杂度，因此，我们对这个问题的求解的复杂度需要严格控制在$O(TN)$范围内，否则会容易超时，因此对于每一组数据，我们的算法复杂度必须要保证为$O(N)$ 这道题的意思就是需要对每一个位置 ，都需要求解位置 到最近的垃圾桶的距离$d_i$，然后对于每一组数据，输出所有的$sum_{i=0}^{n-1}d_i$ 那么对于每一个位置 ，我们设左边离他最近的垃圾桶的距离为$l[i]$，右边离他最近的垃圾桶的距离为$r[i]$，那么则有$d[i]=min(l[i],r[i])$ 对于$r[i]$，我们可以根据题意构建递推表达式： * $s[i]=1$，则有$r[i]=i$ * $s[i]=0$，则$r[i]=r[i+1]$ 初始化$r[n]=10^9$ 同理可以得到$l[i]$的状态转移方程，但是本题可以不使用$l$数组，直接使用一个变量来动态更新即可，具体参考下面代码。 C++(使用cin处理输入会超时，本题需要使用scanf读取) ```c++ #include <bits/stdc++.h> using namespace std; typedef pair<int,int>PII; #define x first #define y second typedef long long ll; const int N=5E5+10,mod=1e9+7; int T,n,r[N]; char s[N]; void solve(int u){ cin>>n; scanf("%s",s); r[n]=1e9; for(int i=n-1;i>=0;i--){ r[i]=(s[i]=='1')?i:r[i+1]; } ll res=0; for(int i=0,pre=-1e9;i<n;i++){ if(s[i]=='1')pre=i; else{ int dist=min(i-pre,r[i]-i); res+=dist; } } printf("Case #%d: %lld

java数据结构基础题型及解法

相关推荐