算法合集(1)

一.双指针1.1 双指针类型双指针(移动零)(1)类型同向双指针快慢指针说明快指针遍历数组慢指针指向下一个非零元素应放置的位置通过交换将零移至末尾。https://blog.csdn.net/2601_95366422/article/details/158542816双指针(复写零)(2)类型同向双指针快慢指针说明先计算复写后数组的长度再用两个指针从后向前复写避免覆盖未处理的数据。https://blog.csdn.net/2601_95366422/article/details/158542904双指针(快乐数)(3)类型快慢指针说明将数字的平方和迭代视为链表用快慢指针检测是否存在循环判断是否最终变为 1。https://blog.csdn.net/2601_95366422/article/details/158543055双指针(盛最多水的容器)(4)类型对撞指针说明左右指针分别指向数组两端计算当前面积移动较短的边向内收缩更新最大面积。https://blog.csdn.net/2601_95366422/article/details/158543063双指针(有效三角形的个数)(5)类型对撞指针说明先对数组排序固定最大边再用对撞指针在剩余区间内寻找满足两边之和大于最大边的组合。https://blog.csdn.net/2601_95366422/article/details/158543070双指针(查找总价格为目标值的两个商品)(6)类型对撞指针说明数组有序左右指针向中间移动寻找两数之和等于目标值。https://blog.csdn.net/2601_95366422/article/details/158578585双指针(三数之和)(7)类型对撞指针说明先排序固定一个数再用对撞指针在剩余区间内寻找两数之和等于目标值。https://blog.csdn.net/2601_95366422/article/details/158578620双指针(四数之和)(8)类型对撞指针说明先排序固定两个数再用对撞指针在剩余区间内寻找两数之和等于目标值。https://blog.csdn.net/2601_95366422/article/details/1585786381.2 双指针的重要知识知识一有效三角形个数关于三角形三条边的验证小学我们就学过任意两边之和必须大于第三边即三个不等式要同时成立abcacbbca不过这里有一个可以优化的地方。如果我们事先知道 c 是三条边中最大的那一条那么验证就可以简化——只需要检查 abc 这一个条件就够了。为什么另外两个不需要再验证因为 c 最大那么 ac 肯定大于 bc 已经比 b 大再加上 a 只会更大同理 bc 也肯定大于 a。所以只要 abc成立剩下两个条件自动就满足了。二.滑动窗口2.1 滑动窗口题目1. 长度最小的子数组类型固定目标的最小窗口说明求满足子数组和 ≥ target 的最短连续子数组。右指针扩展左指针收缩直到和小于 target更新最小长度。链接https://blog.csdn.net/2601_95366422/article/details/1585786532. 无重复字符的最长子串类型最长无重复窗口说明用哈希表记录字符出现次数。右指针移动若字符重复则移动左指针跳过重复字符维护窗口内无重复。链接https://blog.csdn.net/2601_95366422/article/details/1585705993. 最大连续1的个数 III类型允许翻转 k 个 0 的最长窗口说明将问题转化为窗口内 0 的个数 ≤ k求最长窗口。右指针扩展0 的个数超限时左指针收缩。链接https://blog.csdn.net/2601_95366422/article/details/1585781354. 将 x 减到 0 的最小操作数类型转化为最长子数组说明求最长的子数组使其和为总和 - x答案 总长度 - 最长子数组长度。若不存在则返回 -1。链接https://blog.csdn.net/2601_95366422/article/details/1585842205. 水果成篮类型最多两种元素的最长窗口说明用哈希表维护窗口内元素种类种类超过 2 时左指针收缩记录最大窗口长度。链接https://blog.csdn.net/2601_95366422/article/details/1586095276. 找到字符串所有字母异位词类型固定窗口 字符计数说明窗口大小固定为模式串长度用数组统计字符频率。滑动窗口每次比较当前窗口频率是否与目标一致记录起始下标。链接https://blog.csdn.net/2601_95366422/article/details/1586188047. 串联所有单词的子串类型固定窗口 单词哈希说明单词长度固定用哈希表统计单词出现次数。需对起始位置进行多种偏移分别滑动窗口匹配单词计数。链接https://blog.csdn.net/2601_95366422/article/details/1586221258. 最小覆盖子串类型最短覆盖窗口说明用哈希表记录目标字符需求。右指针扩展直到覆盖所有目标字符再收缩左指针寻找最短覆盖窗口。链接https://blog.csdn.net/2601_95366422/article/details/1586559002.2 滑动窗口的概念一、滑动窗口是什么滑动窗口是一种在数组/字符串上维护一个连续区间窗口的技巧。通过不断移动窗口的左右边界来探索满足条件的最优区间。它本质上是一种双指针技巧两个指针左指针left和右指针right都只向一个方向移动因此时间复杂度为O(n)。二、为什么要用滑动窗口很多子数组/子串问题如果使用暴力枚举固定左边界枚举右边界时间复杂度为O(n²)当数据量较大时无法承受。滑动窗口利用“窗口内信息的连续性”在移动左右指针时增量更新窗口状态如和、计数、种类等避免重复计算从而将复杂度降到O(n)。三、什么时候可以用滑动窗口滑动窗口适用于连续子数组/子串问题且窗口的扩大和收缩具有单调性。常见的特征包括求最长/最短满足某种条件的连续子数组。窗口内维护的信息可以快速更新如和、计数、哈希表。当右指针移动时窗口条件可能被破坏此时通过移动左指针来恢复条件即“右进左出”。典型题型如求和 ≥ target 的最短子数组、无重复字符的最长子串、最多包含 k 种字符的最长子串、允许翻转 k 个 0 的最长连续 1 子数组等。掌握滑动窗口的关键是明确窗口内维护的信息是什么以及何时移动左右指针。2.3 重要知识知识二正难则反正难则反是一种常用的解题思路核心思想是当从正面直接解决问题比较困难时可以尝试从反面或对立面入手通过求解反面问题来间接得到正面问题的答案。这就像数学中的反证法——先假设结论不成立然后推出矛盾从而证明原结论成立。三.二分查找3.1 二分查找题目1. 二分查找(1)类型标准二分查找说明在有序数组中查找目标值返回下标不存在则返回 -1。链接https://blog.csdn.net/2601_95366422/article/details/1586579632. 二分查找(在排序数组查找元素)(2)类型左边界与右边界说明给定升序数组和目标值返回目标值的索引若不存在则返回 -1。链接https://blog.csdn.net/2601_95366422/article/details/1586625053. 二分查找(搜索插入位置)(3)类型左边界说明在升序数组中查找目标值的插入位置即第一个大于等于目标的下标。链接https://blog.csdn.net/2601_95366422/article/details/1586909474. 二分查找(x的平方根)(4)类型右边界说明返回非负整数 x 的算术平方根整数部分即最后一个满足mid² ≤ x的值。链接https://blog.csdn.net/2601_95366422/article/details/1587702185. 二分查找(山脉数组的峰顶索引)(5)类型左边界说明山脉数组先升后降找到峰顶索引即第一个满足arr[i] arr[i1]的位置。链接https://blog.csdn.net/2601_95366422/article/details/1587708896. 二分查找(寻找峰值)(6)类型左边界或右边界说明在无序数组中找到任意一个峰值利用nums[mid] nums[mid1]则右移否则左移。链接https://blog.csdn.net/2601_95366422/article/details/1587714477. 二分查找(寻找旋转排序数组中的最小值)(7)类型左边界说明旋转升序数组中找到最小值即第一个小于等于右端点的元素。链接https://blog.csdn.net/2601_95366422/article/details/1587740218. 二分查找(点名)(8)类型左边界说明在升序数组中找出缺失的数字即第一个下标与值不相等的位置。链接https://blog.csdn.net/2601_95366422/article/details/1587765173.2 二分查找的概念二分查找是一种在有序数组中高效查找目标值的算法核心思想是每次将查找区间缩小一半通过不断比较中间元素与目标值确定目标在左半区间还是右半区间从而快速定位。关键要素前提数组必须具有单调性升序或降序即具备二分性——能够通过中点将区间划分为左右两部分并根据规则判断目标所在方向。过程初始化左右指针left和right循环条件left ≤ right或left right取决于模板计算中点mid left (right - left)/2比较nums[mid]与target若相等则返回若小于目标则left mid 1否则right mid - 1。时间复杂度O(log n)远优于线性查找的 O(n)。左边界与右边界在解决重复元素或边界条件问题时二分查找会演变为寻找左边界和寻找右边界的两种模板左边界寻找第一个满足条件的位置如第一个等于 target 的下标。要点中点取向下取整缩进规则为if (nums[mid] target) left mid 1; else right mid;。循环结束后left即为左边界。右边界寻找最后一个满足条件的位置如最后一个等于 target 的下标。要点中点取向上取整mid left (right - left 1)/2缩进规则为if (nums[mid] target) left mid; else right mid - 1;。循环结束后right即为右边界。掌握左右边界模板可处理如“搜索插入位置”、“在排序数组中查找元素的第一个和最后一个位置”等问题。二分性的本质二分查找的前提并非必须是严格单调的数组而是二分性——即存在一个分界点使得区间可以划分为左区域、中点、右区域并且能够通过某种比较规则判断目标位于哪一侧。例如山脉数组先增后减可通过比较mid与mid1判断峰值在左还是在右。旋转排序数组局部有序通过比较中间值与右端点可判断最小值在左半还是右半。函数极值如求平方根、找临界值只要值域具有单调性如mid² ≤ x在左侧成立右侧不成立即可使用二分。因此二分查找的核心是寻找“二分性”而非死记硬背“有序”。只要问题能通过中点将解空间一分为二且能判断目标在哪一侧二分法就适用。四.前缀和4.1 前缀和题目1. 前缀和(一维前缀和模板)(1)类型一维前缀和模板说明预处理前缀和数组快速计算任意区间[l, r]的和公式为sum dp[r] - dp[l-1]。链接https://blog.csdn.net/2601_95366422/article/details/1588040062. 前缀和(二维前缀和模板)(2)类型二维前缀和模板说明预处理二维前缀和快速计算任意子矩阵的和利用容斥原理sum dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] dp[x1-1][y1-1]。链接https://blog.csdn.net/2601_95366422/article/details/1588050443. 前缀和(寻找数组的中心下标)(3)类型前缀和与后缀和说明计算每个位置左侧和右侧元素的和判断是否相等注意边界处理。链接https://blog.csdn.net/2601_95366422/article/details/1588064524. 前缀和(除了自身以外数组的乘积)(4)类型前缀积与后缀积说明计算每个位置左侧所有元素的乘积和右侧所有元素的乘积再相乘得到结果。链接https://blog.csdn.net/2601_95366422/article/details/1588408925. 前缀和(和为K的子数组)(5)类型前缀和 哈希表说明统计和为 k 的子数组个数用哈希表记录前缀和出现次数sum - k的个数即为答案。链接https://blog.csdn.net/2601_95366422/article/details/1588416766. 前缀和(和可被K整除的子数组)(6)类型前缀和 同余定理说明统计子数组和能被 k 整除的个数利用(a-b) % k 0等价于a % k b % k注意负数余数修正。链接https://blog.csdn.net/2601_95366422/article/details/1588426117. 前缀和(连续数组)(7)类型前缀和 哈希表转化说明找含有相同数量 0 和 1 的最长连续子数组将 0 视为 -1问题转化为和为 0 的最长子数组。链接https://blog.csdn.net/2601_95366422/article/details/1588480068. 前缀和(矩阵区域和)(8)类型二维前缀和 边界处理说明计算每个格子周围k × k区域的和利用二维前缀和注意边界越界处理。链接https://blog.csdn.net/2601_95366422/article/details/1588500164.2 前缀和概念前缀和的概念前缀和是一种用于快速计算数组任意区间和的预处理技术核心思想是预先计算出从起点到每个位置的前缀累加值从而将区间和查询的时间复杂度从 O(n) 降为 O(1)。基本思想定义数组arr下标从 1 开始便于处理边界。前缀和数组dp[i]表示arr[1] arr[2] ... arr[i]即前 i 个元素的和。递推公式dp[i] dp[i-1] arr[i]且dp[0] 0。对于任意区间[l, r]区间和 dp[r] - dp[l-1]。时间复杂度预处理 O(n)每次查询 O(1)。一维前缀和一维前缀和适用于一维数组的区间和问题。预处理dp[i] dp[i-1] arr[i]查询sum(l, r) dp[r] - dp[l-1]应用静态数组多次求区间和、子数组和等问题。二维前缀和二维前缀和适用于矩阵的子矩阵和问题。定义dp[i][j]表示从(1,1)到(i,j)的矩形内所有元素之和。递推公式dp[i][j] dp[i-1][j] dp[i][j-1] - dp[i-1][j-1] arr[i][j]利用容斥原理查询对于子矩阵(x1, y1)到(x2, y2)其和为sum dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] dp[x1-1][y1-1]应用静态矩阵多次求子矩阵和、图像处理等。前缀和的扩展应用前缀和不仅限于求和还可以扩展到前缀积、前缀异或、前缀哈希等常用于结合哈希表解决子数组计数问题如“和为 K 的子数组”、“和可被 K 整除的子数组”。通过将问题转化为两个前缀和之间的关系可以高效求解。核心要点空间换时间预处理一次查询 O(1)。灵活变体可配合哈希表、同余定理等处理更复杂的子数组问题。4.3 重要知识同余定理如果两个数 a 和 b的差能被 kk整除那么它们对 k 取余的结果相等即(a−b)%k0 ⟺a % k b % k修正求余在 C 中负数对正数取余的结果是负数例如-1 % 5 -1这与数学上的余数定义不同。因此需要修正修正公式为mod (sum % k k ) % k该公式保证结果始终落在 0,k−1 范围内。