WBY's Blog - 二分法
type: channel
link: https://wbyblog.cn/category/%E4%BA%8C%E5%88%86%E6%B3%95/
items: 2962. 统计最大元素出现至少 K 次的子数组
items: 611. 有效三角形的个数
items: 4. 寻找两个正序数组的中位数
items: 154. 寻找旋转排序数组中的最小值 II
items: 153. 寻找旋转排序数组中的最小值
items: 34. 在排序数组中查找元素的第一个和最后一个位置
items: 69. x的平方根

2962. 统计最大元素出现至少 K 次的子数组
type: item
date: 2025-10-19T21:38:00+08:00
description: 题目链接：https://leetcode.cn/problems/count-subarrays-where-max-element-appears-at-least-k-times/description/我的思路想到用滑动窗口双指针，但是在结果计算和指针移动的判断上还是有些不太对，思路是清晰的，离正确答案之差一点点。首先求出$nums$中的最大值记为$m$，初始化左指针$l=0$，定义一个变量$cnt$统计枚举过程中最大值出现了几次，接着用enumerator枚举$r,x$，如果$x=m$，则将$cnt+1$，当$cnt\geq k$时，进入while循环判断，此时意味着到了某个符合条件子数组的边界，$ans+1$，如果$nums[l]=m$，则将$cnt-1$，同时将左指针右移$l+1$，因为我们要统计的是子数组的个数，所以在考察完每个$r,x$时，再将左指针重置，$l=0$，以免漏掉情况，如此循环判断下去，返回$ans$分析这个思路看上去很正确，但存在考察不全的情况，尽管想到了重置左指针，但由于$cnt$的值动态变化，所以会漏掉计数。比如案例$[1,3,2,3,3], k = 2$，按照上面的思路，将每一步计算的$cnt$值和子数组打印出来得到：2 [1, 3, 2, 3]2 [3, 2, 3]2 [1, 3, 2, 3, 3]2 [3, 2, 3, 3]到这里程序就退出运行了，原因出在考察到第三个3时。在$r=3$时，对应的$nums[3]=3$为第二个3，此时$cnt=2$，满足while循环进入条件，接着开始计数，做指针开始右移，得到一开始的两个结果（前两行），但由于$l$移动到1时，$nums[1]$也是3，因此$cnt-1$，$cnt$变为1，跳出循环，$l$重置为0，继续考察数组元素，$r=4,x=3$，$cnt$再加1，得到$cnt=2$，满足while进入条件，开始计数，得到后面两行的结果，但同样的，当$l$再次移动到1时，$nums[1]=3$，使得$cnt-1$，变成1，不再符合while的条件，便跳出循环了，得到错误的结果。纠正滑动窗口问题中，应该不走回头路，试想当$r=3$时，左指针开始移动，滑动到$l=1$时碰到最大值，那么说明$nums[1]$的这个3不能再用了（不要回头，不然会很复杂），我们要将这种情况下的所有可能全部计算出来，接着考虑后面的元素，每一个元素都如此，便能计算到最准确的结果回到上面那个情况，$r=3,x=3$，进入while判断，$l$到1后$cnt-1$，$l$再加1后跳出循环（因为$l+1$是写在while中的最后一句），此时$l$变为2，那么此时对应的，在右边界为$r=3$的情况下，符合条件的数组数不就是2个吗？因此只需要$ans+l$即可，非常巧妙换句话说，其实我们只要找到每个“临界”情况，再将此时的$l$累加起来，就是最后的答案。再看$r=4$的情况，上一个循环中$l$被赋值为2，那么同样地，$l$会以4跳出while循环，此时对应的符合条件的数组不就是4个嘛，分别是$[1,3,2,3,3],[3,2,3,3],[2,3,3],[3,3]$，因为有最后一个元素的加进来，所以不会考察到与之前重复的情况，最后将4和2相加，6就是最终的答案反思双指针/滑动窗口问题中，一般不会将左指针进行重置，一方面容易考察重复情况产生错误，另一方面思路会不够清晰，容易搞混这题还有一个优化的点是，可以直接利用$k$，节省内存占用，遇到最大值就将其减1，while的循环进入条件为$k=0$，当左指针滑到最大值时，再将$k+1$即可，这样可以节约一些内存其实做题也是一个编码-解码的过程，我们的大脑中存在着latent空间，需要将题目进行解码，知道它是什么意思，同时也要将答案进行编码，二者要在latent上匹配，本质上讲的都是一个东西，二者在高维空间中应该有相似的表示，这样才是最佳的解答结果时间复杂度：$O(N)$空间复杂度：$O(1)$已是最优解

611. 有效三角形的个数
type: item
date: 2025-10-12T12:36:00+08:00
description: 题目链接：https://leetcode.cn/problems/valid-triangle-number/description/我的思路这题是很典型的初中数学题，根据三条边的大小来判断是否能组成一个三角形，想到判断条件为：两边之和大于第三边，两边之差小于第三边。很容易想到暴力枚举法，但这样的效率很低，因此联想到用双指针法，但也没有做进一步的思考，就直接开始动手了纠正首先将nums排序，从中取出已经排好序的三个数$a\leq b\leq c$，那么根据判断条件，要让这三条边能构成一个三角形，有：$a+b>c,a+c>b,b+c>a$，因为已经排好序了，那么后面两个条件必然成立，因此我们的目标转换为判断$a+b$是否大于$c$这里有一个很容易困惑的点，就是第二个条件“两边之差小于第三边”是否能满足？根据上面的讨论，$a+c>b$和$b+c>a$是必然成立的，那么根据这两个式子可以推出：$|b-a|=a-b<c,|b-c|=c-b<a,|a-c|=c-a<b$也必然成立（分别将两个变量移到不等号右边），那么第二个条件天然地满足了，只剩下要判断两个短边的和是否大于长边因此我们可以固定长边，取$c=\mathrm {nums}[i],\forall i\in [2, n-1]$，接着在$[0,i-1]$中进行双指针判断，初始化$l=0,r=i-1$，如果$\mathrm{nums}[l]+\mathrm{nums}[r]>\mathrm {nums}[i]$，就说明从$l$到$r$之间的每个数都满足这个条件，能够构成三角形（因为已经事先排好序），就可以让$ans$加上$r-l$优化这题还有一个更巧妙的操作，但理解起来比较困难，就是用卷积+快速傅里叶变换，numpy包包含了快速傅里叶算法，能有效降低时间复杂度（因为这道题中数组中数字范围小于1000，比较小，因此这个方案可行）。计算不符合条件的情况数（两边之和小于第三边），然后再用一共有几种情况$C_{nums.size}^3$减掉不合理的情况数，就能够得到最终答案，为什么要这样做，通过下面的讨论可以找到答案这里用到了两个关键定理：卷积定理：频域相乘等价于时域卷积，时域卷积等价于频域相乘，即$\mathcal{F}\{f*g\}=\mathcal{F}\{f\}\cdot\mathcal{F}\{g\},\mathcal{F}\{f\cdot g\}=\mathcal{F}\{f\}*\mathcal{F}\{g\}$时域卷积的定义：$(f∗g)[k]=\sum_i​f[i]⋅g[k−i]$，对于每一个可能的和$k$，把所有能组成$i+j=k$的组合的乘积$f[i]g[j]$累加，换句话说可以写成：$(f*f)[s]=\sum_{x+y=s}f[x]f[y]$，表示两数相加和为$s$的组合次数首先构建频率数组，$cnt[x]$表示$x$在所给数组中的出现频次，接着结合快速傅里叶变换做自卷积，得到$cnt2[s]$，表示两边之和为$s$的组合数（可能有几种情况）。参照上面的类似思路，我们固定$cnt$，取其中的元素所对应的边长作为最长边来考虑（考虑的背景是，根据三角形组成判断条件，对每个三元组，最大边必须小于另外两边之和），那么我只需要考察$cnt2[:cnt.size]$这部分的元素，后面的部分没有合理的最长边来与之对应了，因此不在考虑范围内需要注意的是，卷积过程中会出现两种情况：（1）自己加自己；（2）顺序调换相加得到相同结果，这两种情况都会算入到计数中，如下表所示：因此我们需要对$cnt2$中的值进行修正，考虑上面说到的两种情况：自己加自己，相当于把自己*2，因此得到的数一定为偶数，这种情况只会出现在$cnt2$的偶数索引处，因此只需要将$cnt2$偶数位置处的值减掉原来的值$cnt$即可（比如这里$cnt[4]=2$，意味着原来数组中有2个4，$cnt2[8]$中会包含2个自相加的结果，在这道题中我们不能重复利用元素，因此需要减掉2），写成表达式就是：$cnt2[::2]=cnt2[::2]-cnt[:]$，但因为我们上一步中对$cnt2$进行了截取，只取了$cnt.size$这一部分，在取偶数索引部分时，其实只对应了$cnt$的$(cnt.size+1)//2$部分，因此在代码实现时，需要写成$cnt2[::2]-=cnt[:(cnt.size+1)//2]$（以上表为例，$cnt2$被截取$[0:4]$这部分，取偶数索引，对应0,2,4，只有三个元素，这几个元素才会包含自相加的情况，我们为了修正，需要减掉其对应原始数组中元素的出现频次，即0,1,2这三个元素的频次，而在$cnt$中，这三个元素对应前$5+1//2=3$个元素，因此需要这么计算）顺序调换得到相同结果，这种情…

4. 寻找两个正序数组的中位数
type: item
date: 2025-06-04T11:41:00+08:00
description: 题目链接：https://leetcode.cn/problems/median-of-two-sorted-arrays/description/我的思路这是一道困难级别的题，确实非常难，在时间复杂度的限制下，只能采用二分法来进行求解，关键是如何进行二分。自己拿到这题完全没有思路。题解官方题解给了两种办法，一种是直接双指针搜索，判断规则非常复杂，程序也很长，尽管时间复杂度表现很优秀，但还是有点难理解，这里复述另一种解法，切分的思路，因为我们要找的是中位数，统计中，中位数的作用是：将一个集合划分为两个长度相等的子集，其中一个子集中的元素总是大于另一个子集中的元素。假设两个序列的长度分别为m和n，那么于是乎，我们可以尝试划分两个序列，就会每个序列各自得到两个子集，将两个序列前部分子集合并、后部分子集合并，再判断当前切分得是否合理，如果合理，找到前一个合并子集的最大值、后一个合并子集的最小值，返回平均值（当m + n为偶数时），或直接返回前一个合并子集的最大值（当m + n为奇数时）。这样的思路里有两个地方需要进一步讨论：1. 如何划分子集？ 2. 如何判断划分得是否合理？接下来逐步讨论这两个问题：如何划分子集令两个序列分别为A, B，那么假设我们在序列A的i索引处切一刀，B的j索引处切一刀，那么我们就可以得到下面的切分：$A[0]\cdots A[i-1]\ |\ A[i]\cdots A[m-1]$$B[0]\cdots B[j-1]\ |\ B[j]\cdots B[m-1]$A中有m个元素，所以一共有m + 1种切分办法，对应地B能有n + 1种切分办法我们把$A[0]\cdots A[i-1]$和$B[0]\cdots B[i-1]$放到一起，称为left_part，剩下的$A[i]\cdots A[m-1]$和$B[j]\cdots B[n-1]$放到一起，称为right_part如何判断切分得合理根据统计中中位数的定义，如果我们的划分合理，那么应该满足：$\max(left\_part)\leq \min(right\_part)$$len(left\_part)=len(right\_part)\ or \ len(right\_part)+1$其中第一条是无论m + n是奇数还是偶数都共同满足的，第二条要分情况，当m + n为偶数时，则取前一个条件，反之取后一个条件，只有这样，才是“恰好”切分，长度上符合要求，数值上也符合要求（不然比如[1,2,3,4|10]和[1,2|9,11]，这样也能满足第一条条件，但并不是最佳的切分，因此还要加上第二条条件）现在我们已经归纳出了两个必要的条件，那么代码实际操作起来该怎么写呢？代码离不开数学表示，有了文字的概念表述，还需要将这些表述进一步转化为数学表达式，才能清晰地在代码中体现和实现算法。根据上面的描述，我们可以得出：$i+j=m-i+n-j$ 或 $i+j=m-i+n-j+1$上述两式分别对应m + n为偶数和奇数时，也就是上面第二点中的第二个条件，对这个式子进行简化，把i + j全部移到一边，可以得到：$i+j=\lfloor\frac{m+n+1}{2}\rfloor$通过向下取整操作，可以将两个式子用上式直观地表达出来，无论m + n是奇数还是偶数，直接代入计算即可。为不失一般性，我们先假设m ≤ n，也就是A的长度小于等于B的长度，于是乎i的取值范围满足$0≤i≤m$（为什么是到m，因为根据第1点的讨论，对于m长的序列而言，有m + 1种划分方法，这里我们不再是二分索引位置，因此范围不是从0到m - 1），那么我们只需要在这个范围内枚举i，即可求得$j=\lfloor\frac{m+n+1}2\rfloor-i$，不需要再加入额外的判断条件了。这种情况下，如果A的长度更长，则只需要交换A和B就行了。但是这种情况下（也是二分法中常见到的特殊情况，就是边界值），i和j有可能触碰到边界值m和n或0，直接获取A[m]会out of index，或A[i-1]即A[-1]会取错值，不符合我们的算法要求，因此需要对这几种情况来进行处理。实际上i和j只代表了划分点的位置，但是在程序里我们要依靠i和j的实际值来取出序列种对应位置的元素值进行判断，比如假设i = 0，那么A的划分点为0，此时A[-1]是不存在的，因为整个序列A都被划进了right_part里，但是根据我们上面的假设，我们又要取A[-1]来作为我们判断left_part里最大值的依据，就会出现错误。处理这种情况的办法其实也很简单，只需要规定：$A[-1]=B[-1]=-\infty, A[m]=B[n]=\infty$即可，理解起来也很简单：当一个数组不出现在前一部分时，对应的值为负无穷，就不会对前一部分的最大值产生…

154. 寻找旋转排序数组中的最小值 II
type: item
date: 2025-05-14T13:25:00+08:00
description: 题目链接：https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array-ii/description/我的思路基本上是延续153题的思路，但和153题不一样的是，这题中可能会有重复的相同元素出现，因此需要多加思考。考虑到的可能情况为：[3,3,1,3], [10,1,10,10,10]，nums[mid] >或< nums[r]的情况比较好解决，和153中的思路一样，但当二者相等时，要如何处理呢？一开始只想到了笨方法，有灵光一现想到只要考虑右边即可（因为原数组已经是按非递减顺序排好），但没有抓住这个思路继续想下去，而是继续尝试笨方法：分情况讨论。数值相同的情况可能有几种，比如[3,3,1,3]，l在0处，r在3处，mid = 1，以及[10,1,10,10,10]，l在0处，r在4处，mid = 2，那很自然想到说要判断一下mid前后的数值情况，如果nums[mid - 1] == nums[mid]，那就从左边缩短区间，l = mid + 1，如果nums[mid + 1] == nums[mid]，那就从右边缩短区间，r = mid - 1但是，这样的思路卡在[1,1]上，mid = 0，nums[-1]仍然为1，会进入死循环。于是乎再尝试加入判断条件l - r ≠ 1，才进入这样的判断，但是又卡在了[1,1,0,1,1,1,1,1,1,1,1,1]上，起初l = 0, r = 11, mid = 5，因为条件语句首先会判断nums[mid - 1]是否和nums[mid]相等，因此在此先执行了此条判断，返回值为True，于是乎改变了l = mid + 1 = 6，直接把正确答案给略过了。这样的办法还是不行，卡在了当元素相同时的左右取舍上。于是乎又想到另一个办法，写一个子函数来判断序列的片段[l:nums+1]和[nums:r]是否都为相同元素，然后将全部为相同元素的那一边进行缩短。这样一来，整个程序又成了屎山代码，又臭又长。纠正被狠狠思维定势住了改变左右边界，不一定要基于mid来改，在这道题的情境下这样做很容易把正确答案给直接略过了，步子不要跨那么大，我每次只走1步，那样也是可以的，把r = mid - 1改成r -= 1，每次都改一点点，因为旋转前的原序列是非递减的，因此我们只需要不断改右边就好反思唉，还是得多练练结果0ms 100%, 17.91MB 62.5%

153. 寻找旋转排序数组中的最小值
type: item
date: 2025-05-08T19:32:00+08:00
description: 题目链接：https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/description/我的思路经历了第34题的摧残后，这道题显得没有那么难了，拿到题目读了一下题意和要求后稍微调整了一下解法就顺利通过了，结果表现也还不错。但还是把这题记录下来，是其中有一个地方和34中不太一样，就是当nums[mid]<nums[r]时，应该将mid直接赋给r，而不是mid-1，解释：因为在这里我们要找到的时最小值，nums[mid]<nums[r]可能会存在于下面的情况：…18…3,1,2…9…，此时l位于18处，r位于9处，mid指向1，而1的前面是3，1就是我们要找的最小值了，因此不能把此时mid这个位置的元素给排除掉（我们之前mid-1就是因为从mid起，包括mid在内的右边部分全部没用了，所以才这么赋值），此时mid指向的位置就是r的最小值了，区间不能再从右边往里面缩了，之后的判断操作也只能从左边开始缩区间结果0ms 100%, 17.63MB 94.39%

34. 在排序数组中查找元素的第一个和最后一个位置
type: item
date: 2025-05-06T09:49:00+08:00
description: 题目链接：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/我的思路大前提：序列已经按非递减顺序排列好。题目要求时间复杂度只能为$O(\log n)$，因此不能用简单的指针法（那样的复杂度为n），只能用二分法来求解。用两次二分法，第一次找第一个出现的位置，第二次找最后一个出现的位置，二分法的时间复杂度本身就为$O(\log n)$，用两次加起来$O(\log n)+O(\log n)$也仍然是$O(\log n)$target出现位置肯定满足条件nums[mid] == target，但也需要进一步判断：第一次出现位置：mid == 0 or nums[mid - 1] < target （有可能回到了列表起点），如果都不符合，那说明nums[mid - 1] = target（这个时候不可能是>target了，否则和先决条件nums[mid] == target以及非递减序列的大前提矛盾），意味着此时的mid还不够靠左，要把mid值往左边移，因此r = mid - 1最后出现位置：mid == len(nums) - 1 or nums[mid + 1] > target （有可能到了列表末尾）当nums[mid] > target时，应该缩短右侧区间，即r = mid - 1，继续做判断，当nums[mid] < target时，应该缩短左侧区间，l = mid + 1思路很明确，但是在执行的时候，还是卡在了如何更新l和r上，要么是选取不合理返不回正确的结果，要么是取值不当让程序陷入死循环纠正始终记住：mid永远在l和r的中间，l和r才是边界。区间的变化无非两种情况，可以通过判断mid值的移动趋势来执行操作，这也是二分法的核心所在：要把mid值往左移动，意味着要从右边缩小区间，因此应该改右边界r = mid - 1（如果把此时的l移动到mid或者mid-1，无论怎样都相当于把l给扩大了或者不变，扩大的情况会让mid值更大，不满足题意，不变的话就会让程序陷入死循环）在这道题里，nums[mid] > target，说明区间“往右伸”得太多了，因此肯定要从右边开始缩减，此时mid和mid之后范围的数值都没有用了，因此除开这些没用的数值，r = mid - 1，这就是-1的由来，如下图所示（注意，这里的坐标轴指的是索引，不是代表序列中的数值，target表示的是target所在的位置）要把mid值往右移动，说明要从左边缩小区间，因此应该改左边界l = mid + 1（如果把此时的r移动到mid或者mid+1，那就相当于把r给缩小了，会让mid值更往左靠，不满足题意）同样地，nums[mid] < target，说明区间“往左伸”得太多了，因此肯定要从左边开始缩减，此时mid和mid之前范围的数值都没有用了，因此除开这些没用的数值，l = mid + 1，这就是+1的由来反思一定要仔细仔细读题，充分利用好题目中的所给条件，并读懂题意，看懂要求，已经好几次没有好好利用题目里给的“非递减序列的条件了序列”的条件了要学习算法复杂度的表示方法，不然在有的题目里会有限制，看不懂培养抽象思维，将问题进行抽象表达，找到共性的特点可以让代码尽可能简单一些（当然，这是进阶要求，现阶段对自己的要求还是能顺利通过解答即可），这道题里一开始的思路是要判断两次，那会很容易想到写两个子函数，但其实这两个子函数有很大篇幅的share部分，统统单独写出来就会篇幅很长不够简洁，完全可以写到一个函数里面结果0ms 100%, 18.74MB 54.33%

69. x的平方根
type: item
date: 2025-05-03T16:34:00+08:00
description: 题目链接：https://leetcode.cn/problems/sqrtx/description/我的思路明显的用二分法的问题，根据教材提示，已知输入为$x$，问题可转化为求$f(y)=y^2-x$的零点问题，可得$f(0)=0-x=-x<0, f(x)=x^2-x>0$，于是我们可以把初始区间定为$[0,x]$，然后开始二分。回顾一下二分的核心思想，不断缩短考察的区间，二分二分，顾名思义要取中间值$mid=(0+x)/2$，之后再判断$f(mid)$是大于0还是小于0，如果大于0，即$mid^2>x$，那就把区间设置为$[0,mid]$，如果小于0，即$mid^2<x$，那就把区间设置为$[mid,x]$，接着继续取新的二分中间值$mid_1=(l+r)/2$，这里的l和r分别代表了区间的左右边界值但是，卡在了这里，一开始只要找到了$mid^2<x$的值，就把mid作为结果返回，但后来发现这样不对，就不知道该怎么确定结果值了。这样的思路会让程序陷入死循环，或者直接返回更小的那个符合题意得值（比如x=6，二分会让程序跳到1，返回1，但应该是2），问题出在了区间的选取上，默认为闭区间，就会很容易出问题。比如x=10，那么程序运行过程如下：l = 0, r = 10, mid = 5, mid^2 = 25 > 10, so r = midl = 0, r = 5, mid = 2, mid^2 = 4 < 10, so l = midl = 2, r = 5, mid = 3, mid^2 = 9 < 10, so l = midl = 3, r = 5, mid = 4, mid^2 = 16 > 10, so r = midl = 3, r = 4, mid = 3, mid^2 = 9 < 10, so l = midl = 3, r = 4, mid = 3, mid^2 = 9 < 10, so l = mid…如此循环下去，陷入死循环，因此这样的确定l和r的方式肯定是不对的，那么如何解决呢？纠正闭区间不行，那我们就设置成开区间咯，我们一个个来试试，比如首先试左闭右开，仍以上面的例子为例，x=10，一开始仍把区间设置为$[0,10]$，但在循环过程中改成左闭右开来避免上面的问题出现。当二分到$mid^2<x$时，就把此时的mid记录为ans，如果这是最后一次二分，那么说明这个肯定是最优解。那实际该如何操作呢？因为这题里我们面对的操作对象全部是整数，因此开区间情况下，只需要把数值-1列为端点即可，比如当区间变化为$[0,5)$时，我们只需要取l = 0, r = 5-1 = 4即可，按这样的思路，我们再过一遍流程：l = 0, r = 10, mid = 5, mid^2 = 25 > 10, so r = mid - 1 = 4l = 0, r = 4, mid = 2, mid^2 = 4 < 10, so l = mid, ans = 2l = 2, r = 4, mid = 3, mid^2 = 9 < 10, so l = mid, ans = 3l = 3, r = 4, mid = 3, mid^2 = 9 < 10, so l = mid, ans = 3…显然这样的办法还是不行，同样地，左开右闭也行不通，那就只剩全开区间了，在设置新区间时，端点全部移动1位（l+1，r-1），按这样的思路我们再来一次：l = 0, r = 10, mid = 5, mid^2 = 25 > 10, so r = mid - 1 = 4l = 0, r = 4, mid = 2, mid^2 = 4 < 10, so l = mid + 1 = 3, ans = 2l = 3, r = 4, mid = 3, mid^2 = 9 < 10, so l = mid + 1 = 4, ans = 3l = 4, r = 4, mid = 4, mid^2 = 16 > 10, so r = mid - 1 = 3l = 4, r = 3, l > r, 溢出，程序结束，ans = 3这样一来便行得通了，而且这样的方法为我们判断程序结束创造了条件，while的条件应为l≤r，当l>r时，便结束程序，输出此时的ans反思对二分的概念一定要掌握清楚绝大多数情况下，开区间还是闭区间都能找到答案，但像此题一样，有时候还是找不到解，就要尝试换一种区间模式，平时写代码时，尽可能养成习惯，如适配Python的程序规则，使用左闭右开区间结果12ms 19.54%, 17.29MB 99.16%