晚上刷到 LeetCode 第 430 场周赛的题单3453 题分割正方形 I排在中等档。说实话刚看到这个标题时我是有点戒备的正方形、分割、计算几何这几个词凑在一起很容易让人以为要上叉积、极角排序、半平面交之类的东西。但认真把题面读完就会发现它就是一道披着几何外衣的计数题核心只需要一句话把二维平面上的点沿着分割线压到一维然后用前缀和扫一遍。这篇题解主要想帮大家把这个拆假动作的过程讲清楚顺便把周赛里这类中等题的通用套路做一个总结。无论你是刚开始刷 LeetCode 的中等题还是已经在冲周赛三题、四题这篇应该都能给你一些有价值的思路。1. 这题难在哪先拆题面再说解法1.1 一句话定位它不是计算几何我按 LeetCode 这类分割正方形系列最常见的设定来理解这道题给定一个左下角在 (0,0)、右上角在 (n,n) 的正方形里面有若干个点每个点坐标都是整数。题目要我们在 x k 的位置画一条竖线k 是整数且 1 k n把正方形切成左右两块。竖线左侧x k 的点记为 L 个右侧x k 的点记为 R 个问所有可能的 k 里面|L - R| 的最小值是多少。这个设定不一定和原题每个字都一样但算法骨架是所有变体都通用的你可以把它当成一个规范化后的题目来看。最重要的是分割线是平行于坐标轴的竖线不是任意角度的斜线。一旦确定这一点整道题的计算复杂度就降了一个维度——我们不需要算面积、不需要判断点在直线哪一侧只需要比较点的横坐标和分割线位置的大小关系。很多同学看到正方形就联想到几何题这是被题目名字带偏了。真正的几何难点在于处理任意直线与多边形的关系而这里的竖线简单到就是一个阈值。我刷题这么多年最深的体会是中等题很少真的考你高深算法更多是考你能不能识破题目的虚张声势。1.2 中等题的价值练的是问题转化这道题难吗从代码量来看一点都不难难的是能不能在 30 秒内看穿它的真面目。LeetCode 热门 100 题大家都刷过里面大量题目其实都在考问题转化。比如二维矩阵前缀和本质上就是把矩形求和变成 O(1) 的查表这道题就是把正方形内点数量的左右对比变成一维数组上的前缀差。你做它的时候真正要训练的不是某个花哨的数据结构而是把几何对象映射成序列的直觉。另外从周赛出题规律来看分割正方形 I大概率是一个系列的开头。题目后缀写着 I说明后面很可能还有 II、III会逐渐加入非整数分割线、带权点、最优位置选择等限制。中等难度的第一题往往是给整个系列打地基的所以它的解法一定足够简单、足够通用。把这道题的模型吃透后面遇到同系列的加强版你至少能立刻知道该往哪个方向想。2. 建立模型把正方形变成一维数组2.1 常见设定坐标、分割线与统计口径把题面拆成几个要素就好下手了正方形边长 n坐标范围是 [0, n]。点集 points每个点是 (x, y)全部在正方形内部或边界上。分割线 x k要求 k 为整数并且 1 k n。左侧点数 L count(x k)右侧点数 R count(x k)。这里最值得注意的是竖线上的点也就是 x k 的那些点到底算哪边。我在这道题里采用的口径是竖线上的点不计入任何一侧。也就是说L R cnt[k] total其中 cnt[k] 表示横坐标恰好等于 k 的点数。这个口径的最大好处是公式特别干净用前缀和一眼就能写出来。当然不同题目对这种边界情况的定义可能不一样。有的题目会规定竖线上的点算左侧那公式就要微调有的题目可能根本不允许点出现在分割线上那建 cnt 数组时就要额外处理。比赛时最忌讳的就是闷头写代码把边界情况拍脑袋定了。我的习惯是先花十秒钟把统计口径在草稿纸上写清楚再动手这一个习惯帮我避开了很多隐蔽的 WA。2.2 核心观察只有 x 坐标有用竖线是垂直于 x 轴的所以每个点对答案的贡献完全由它的 x 坐标决定y 坐标在这一问里从头到尾用不上。这个观察非常重要它是二维转一维的合法性来源。拿到题第一件事就是把 points 里所有点的 x 抽出来按坐标归类。这一步只用 O(m) 时间就能完成cnt [0] * (n 1) for x, y in points: cnt[x] 1 total len(points)cnt[x] 表示横坐标恰好等于 x 的点有多少个。有了这个数组后面无论 L、R 怎么算都只是对 cnt 的区间求和不再需要关心任何点的具体位置。这就是从几何题到数组题的关键一步。这种丢掉无用维度的思路在很多题里都能用到。比如二维平面上找曼哈顿距离最近的点对可以把 xy 和 x-y 拆开比如矩阵中找最大全 1 子矩形可以按行压缩成一维直方图。说到底算法题里的高维对象绝大多数都藏着低维的本质关键是找到那个不变的主轴。这道题的主轴就是横坐标。3. 标准解法排序或用前缀和二选一3.1 前缀和推导从 cnt 到 pre我们先对 cnt 求前缀和数组 pre定义 pre[i] cnt[0] cnt[1] ... cnt[i]也就是所有 x i 的点数。有了 pre任意区间的点数都能在一瞬间算出来左侧点数 L对应 x k等价于 x k - 1所以 L pre[k - 1]右侧点数 R对应 x k等于总数 total 减去 x k 的点数而 x k 的点数就是 pre[k]包括左侧点和竖线上的点所以 R total - pre[k]。这里建议停下来想一下为什么右侧用 pre[k] 而不是 pre[k-1]因为竖线上还有 cnt[k] 个点它们不算左侧也不算右侧所以必须从总数里一并扣掉。这个细节可以出一道经典的面试追问答得上来才算真的理解前缀和的作用。于是每个分割线 k 对应的差值就是 |(pre[k - 1]) - (total - pre[k])|我们扫一遍取最小值即可。3.2 手推一个小例子n5 的完整过程光讲公式容易飘我拿一个具体例子走一遍。设 n 5points [(1,2),(1,4),(3,1),(4,3)]。先统计 cntcnt[0] 0cnt[1] 2两个点的横坐标都是 1cnt[2] 0cnt[3] 1cnt[4] 1cnt[5] 0total 4。求前缀和 prepre[0] 0pre[1] 0 2 2pre[2] 2 0 2pre[3] 2 1 3pre[4] 3 1 4pre[5] 4 0 4逐个枚举 k 1, 2, 3, 4kL pre[k-1]R total - pre[k]|L - R|1pre[0] 04 - pre[1] 222pre[1] 24 - pre[2] 203pre[2] 24 - pre[3] 114pre[3] 34 - pre[4] 03最小差值在 k 2 时取到答案是 0。也就是说在 x 2 的位置切一刀左边两个点、右边两个点刚好平分。3.3 代码实现Python 和 C 双版本思路理清之后代码其实短得可怜。Python 版本如下from typing import List def min_split_difference(n: int, points: List[List[int]]) - int: cnt [0] * (n 1) for x, y in points: cnt[x] 1 total len(points) # 前缀和pre[i] 表示 x i 的点数 pre [0] * (n 1) for i in range(n 1): pre[i] cnt[i] (pre[i - 1] if i 0 else 0) ans 10 ** 18 for k in range(1, n): left pre[k - 1] # x k right total - pre[k] # x k ans min(ans, abs(left - right)) return ans if ans ! 10 ** 18 else 0C 版本也不复杂习惯了用数组直接模拟class Solution { public: int minSplitDifference(int n, vectorvectorint points) { vectorint cnt(n 1, 0); for (auto p : points) { cnt[p[0]]; } int total points.size(); vectorint pre(n 1, 0); for (int i 0; i n; i) { pre[i] cnt[i] (i 0 ? pre[i - 1] : 0); } int ans INT_MAX; for (int k 1; k n; k) { int left pre[k - 1]; int right total - pre[k]; ans min(ans, abs(left - right)); } return ans INT_MAX ? 0 : ans; } };复杂度方面统计 cnt 需要遍历所有点 O(m)求前缀和和枚举 k 都是 O(n)整体时间复杂度 O(n m)额外空间是 O(n)。放在 n 和 m 都是十万级的数据范围内毫无压力。这种效率也解释了为什么最优解不需要二分整个搜索空间本来就只有 n-1 个整数位置线性扫一遍是最直接、最不可能写错的方案。3.4 边界问题为什么 k 只能取 1 到 n-1有几个边界条件值得单独拿出来说因为它们在周赛里害人无数。第一k 不能取 0 也不能取 n。k 0 时竖线与正方形左边重合根本没有分割出左右两块k n 时同理。题目要求的分割必须让左右两边都包含一部分正方形内部所以可选的 k 就是 1 到 n-1。第二当 total 0 时也就是正方形内一个点都没有那么任意分割线两侧都是 0差值为 0答案自然是 0。第三注意 pre 数组的长度是 n1循环里访问 pre[k] 时 k 最大是 n-1所以不会越界但如果把 n 理解成点的个数而不是边长就非常容易搞混。我建议做题前先看清楚题面里 n 到底是正方形的边长还是点的数量这个理解误差可以直接导致数组开错。4. 变体与进阶从分割正方形 I往后续题目想4.1 如果竖线上的点也被计入某一侧前面我采用了竖线上的点不算的口径但实际周赛里完全可能改成竖线上的点算左侧或者算右侧。这个微调对算法主体没有影响只影响 L 和 R 的表达式。如果竖线上的点算左侧L pre[k]R total - pre[k]也就是所有点都被严格分到左边或右边竖线上的点归左。这时差值就是 |2 * pre[k] - total|扫描时直接用这个式子。如果算右侧L pre[k-1]R total - pre[k-1]同理。我的建议是不要背公式而是记住一个原则先明确 cnt[k] 归哪边再让 L 和 R 的表达式覆盖所有点保证 L R total。只要这个等式成立你的统计口径就是自洽的怎么定义都是安全的。4.2 如果允许任意实数坐标的竖线这是分割正方形 II很喜欢玩的升级。竖线位置 k 不再限定为整数而是可以在 (0, n) 区间内取任意实数。此时差值函数 |L(k) - R(k)| 会变成一个关于 k 的阶梯函数只有当 k 扫过某个点的横坐标时左侧点数才会加一右侧点数才会减一其余区间内差值保持不变。处理这类问题的核心工具是区间合并和差分数组。具体思路是把所有点的横坐标排序然后枚举每一个相邻关键点之间的开区间区间内任意取 k 效果完全一样。找出差值最小的区间即可。更进一步如果存在一段区间使得 L R那就说明可以在该区间内任选一个实数位置答案是 0。这种连续化的思路在《爱吃香蕉的狒狒》LeetCode 073 那类二分答案题里面也很常见本质上都是在连续区间上找满足条件的点只是一个是二分一个是扫区间。4.3 如果改成求能达到最小差值的分割线数量还有一种常见问法不要最小值问在 1 到 n-1 中有多少个整数 k 可以让 |L - R| 等于最小值。这个改动对代码来说几乎是免费的只需要在扫描时多维护一个计数器遇到更小差值时重置为 1遇到相等差值时加一。这类最优解计数的题目在周赛 Q3 里面经常出现难度不高但考察细节很多人会在重置逻辑上漏写一个条件。我写这类题的习惯是先用一个变量维护当前最优值再用另一个变量维护达到最优值的方案数每次更新时先判断是否更优再判断是否相等顺序不能反。4.4 如果点的坐标大到不能开数组当 n 达到 10^9 级别cnt 数组长度根本开不下。这时候就要放弃按坐标开桶的思路改成排序加双指针。具体做法把所有点的 x 坐标排序从左往右扫描分割线位置维护一个指针不断把 x 小于当前 k 的点纳入 L同时用总数减去 L 和竖线上点的数量得到 R。排序 O(m log m)空间 O(m)完全避开 n 的规模。这一招在离散化问题里是必会的。数组能开下的时候用桶数组开不下的时候用排序本质都是把横坐标压缩成有序序列。很多中等题和困难题的分水岭就在这里不是算法变了而是数据结构能不能承受数据的规模。5. 周赛实盘这类题的提速技巧与常见坑5.1 读题 30 秒锁定一维化经过上面这些分析你应该发现这类题有一个非常明显的识别信号正方形、点集、平行于坐标轴的切割线、计数。只要这四要素同时出现九成是一道一维化加前缀和的题。比赛时看到这种题我会在草稿纸上快速画一个数轴把点按横坐标标上去然后问自己三个问题点是否只靠一维坐标区分切割线位置是否离散能否用前缀和表示两侧统计量三个问题回答完解法基本就定了。我特别想强调先写暴力再优化这种实战策略。如果你在比赛里一时想不出前缀和可以先写一个 O(n*m) 的暴力枚举确认题目理解正确然后再把内层循环用前缀和换掉。这个过程看起来多花了五分钟实际上比直接对着空编辑器发呆要快得多。很多时候暴力解法本身就是最好的调试工具它能帮你逼出所有边界条件。5.2 常见报错与排查实录我把这道题容易踩的坑整理成了一张速查表都是我真实犯过的错误供你参考症状可能原因解决办法数组越界把边长 n 和点数 m 搞混cnt 开小了确认变量含义cnt 长度按 n1 开答案一直偏大竖线上的点没从 total 里扣掉检查 R total - pre[k] 是否用了 pre[k]k 取 0 或 n 也算进去了没注意题目要求分割必须把正方形切开循环范围写成 range(1, n)大 n 时答案错误用 int 存累加结果溢出Python 不担心C 用 long long总点数为 0答案异常没有单独处理 total 0 的情况返回 0最小值没更新ans 初始值不够大初始化为 10^97 或 INT_MAX还有一个非常隐蔽的坑当 cnt[x] 本身很大时pre 数组的中间值可能超过 int 范围。LeetCode 的题一般会卡这个所以你哪怕只是求最小差值也建议在 C 里直接开 long long不要省这一点内存省下来的时间可以多调试两个用例。5.3 和二分答案题的内在联系可能有人会问这题能不能二分答案是能但没必要。如果题目问的不是最小值而是是否存在某个 k 使得左侧点数大于等于某一个目标值那就可以二分 k每次用 pre 数组判断当前左侧点数是否达标。这正好是 LeetCode 073《爱吃香蕉的狒狒》那类二分答案题的处理方式给定一个目标判断当前阈值是否满足条件。这两种思路的边界处理也有相似之处。二分题里最容易错的是到底是 left right 还是 left right以及中点 mid 是否可能陷入死循环。前缀和题里最容易错的是左右两侧是否覆盖了所有点。本质上它们都在考同一件基本功对离散边界的精确理解。把这道题和 073 那道题放在一起对比着做你会发现所谓的中等题套路都是相通的。最后说点题外话我个人在实际操作中的体会是LeetCode 周赛的中等题从来不靠偏题怪题取胜它赢在误导——用看起来复杂的包装掩盖一个简单的模型。3453 这道分割正方形 I就是非常标准的例子你把正方形外衣一脱里面的内容就是一个一维计数。这种题做多了之后遇到任何分割区域点集相关的题目我都会先问自己一句这个问题是不是可以降维答案一旦变成是剩下的就是把排序、前缀和、二分这些基本功拿出来稳稳地写。如果你正准备备战周赛或者刷题瓶颈期建议把这题的变体都练一遍整数竖线、实数竖线、横线分割、求数量、离散化。每多练一种变体你对这类题的理解就会深一层。刷题本来就是个拼图游戏这题可能只是你拼图里的一小块但有了它旁边几块也会跟着变得清晰。 LeetCode 3453分割正方形I：一维化前缀和破解计数题
晚上刷到 LeetCode 第 430 场周赛的题单3453 题分割正方形 I排在中等档。说实话刚看到这个标题时我是有点戒备的正方形、分割、计算几何这几个词凑在一起很容易让人以为要上叉积、极角排序、半平面交之类的东西。但认真把题面读完就会发现它就是一道披着几何外衣的计数题核心只需要一句话把二维平面上的点沿着分割线压到一维然后用前缀和扫一遍。这篇题解主要想帮大家把这个拆假动作的过程讲清楚顺便把周赛里这类中等题的通用套路做一个总结。无论你是刚开始刷 LeetCode 的中等题还是已经在冲周赛三题、四题这篇应该都能给你一些有价值的思路。1. 这题难在哪先拆题面再说解法1.1 一句话定位它不是计算几何我按 LeetCode 这类分割正方形系列最常见的设定来理解这道题给定一个左下角在 (0,0)、右上角在 (n,n) 的正方形里面有若干个点每个点坐标都是整数。题目要我们在 x k 的位置画一条竖线k 是整数且 1 k n把正方形切成左右两块。竖线左侧x k 的点记为 L 个右侧x k 的点记为 R 个问所有可能的 k 里面|L - R| 的最小值是多少。这个设定不一定和原题每个字都一样但算法骨架是所有变体都通用的你可以把它当成一个规范化后的题目来看。最重要的是分割线是平行于坐标轴的竖线不是任意角度的斜线。一旦确定这一点整道题的计算复杂度就降了一个维度——我们不需要算面积、不需要判断点在直线哪一侧只需要比较点的横坐标和分割线位置的大小关系。很多同学看到正方形就联想到几何题这是被题目名字带偏了。真正的几何难点在于处理任意直线与多边形的关系而这里的竖线简单到就是一个阈值。我刷题这么多年最深的体会是中等题很少真的考你高深算法更多是考你能不能识破题目的虚张声势。1.2 中等题的价值练的是问题转化这道题难吗从代码量来看一点都不难难的是能不能在 30 秒内看穿它的真面目。LeetCode 热门 100 题大家都刷过里面大量题目其实都在考问题转化。比如二维矩阵前缀和本质上就是把矩形求和变成 O(1) 的查表这道题就是把正方形内点数量的左右对比变成一维数组上的前缀差。你做它的时候真正要训练的不是某个花哨的数据结构而是把几何对象映射成序列的直觉。另外从周赛出题规律来看分割正方形 I大概率是一个系列的开头。题目后缀写着 I说明后面很可能还有 II、III会逐渐加入非整数分割线、带权点、最优位置选择等限制。中等难度的第一题往往是给整个系列打地基的所以它的解法一定足够简单、足够通用。把这道题的模型吃透后面遇到同系列的加强版你至少能立刻知道该往哪个方向想。2. 建立模型把正方形变成一维数组2.1 常见设定坐标、分割线与统计口径把题面拆成几个要素就好下手了正方形边长 n坐标范围是 [0, n]。点集 points每个点是 (x, y)全部在正方形内部或边界上。分割线 x k要求 k 为整数并且 1 k n。左侧点数 L count(x k)右侧点数 R count(x k)。这里最值得注意的是竖线上的点也就是 x k 的那些点到底算哪边。我在这道题里采用的口径是竖线上的点不计入任何一侧。也就是说L R cnt[k] total其中 cnt[k] 表示横坐标恰好等于 k 的点数。这个口径的最大好处是公式特别干净用前缀和一眼就能写出来。当然不同题目对这种边界情况的定义可能不一样。有的题目会规定竖线上的点算左侧那公式就要微调有的题目可能根本不允许点出现在分割线上那建 cnt 数组时就要额外处理。比赛时最忌讳的就是闷头写代码把边界情况拍脑袋定了。我的习惯是先花十秒钟把统计口径在草稿纸上写清楚再动手这一个习惯帮我避开了很多隐蔽的 WA。2.2 核心观察只有 x 坐标有用竖线是垂直于 x 轴的所以每个点对答案的贡献完全由它的 x 坐标决定y 坐标在这一问里从头到尾用不上。这个观察非常重要它是二维转一维的合法性来源。拿到题第一件事就是把 points 里所有点的 x 抽出来按坐标归类。这一步只用 O(m) 时间就能完成cnt [0] * (n 1) for x, y in points: cnt[x] 1 total len(points)cnt[x] 表示横坐标恰好等于 x 的点有多少个。有了这个数组后面无论 L、R 怎么算都只是对 cnt 的区间求和不再需要关心任何点的具体位置。这就是从几何题到数组题的关键一步。这种丢掉无用维度的思路在很多题里都能用到。比如二维平面上找曼哈顿距离最近的点对可以把 xy 和 x-y 拆开比如矩阵中找最大全 1 子矩形可以按行压缩成一维直方图。说到底算法题里的高维对象绝大多数都藏着低维的本质关键是找到那个不变的主轴。这道题的主轴就是横坐标。3. 标准解法排序或用前缀和二选一3.1 前缀和推导从 cnt 到 pre我们先对 cnt 求前缀和数组 pre定义 pre[i] cnt[0] cnt[1] ... cnt[i]也就是所有 x i 的点数。有了 pre任意区间的点数都能在一瞬间算出来左侧点数 L对应 x k等价于 x k - 1所以 L pre[k - 1]右侧点数 R对应 x k等于总数 total 减去 x k 的点数而 x k 的点数就是 pre[k]包括左侧点和竖线上的点所以 R total - pre[k]。这里建议停下来想一下为什么右侧用 pre[k] 而不是 pre[k-1]因为竖线上还有 cnt[k] 个点它们不算左侧也不算右侧所以必须从总数里一并扣掉。这个细节可以出一道经典的面试追问答得上来才算真的理解前缀和的作用。于是每个分割线 k 对应的差值就是 |(pre[k - 1]) - (total - pre[k])|我们扫一遍取最小值即可。3.2 手推一个小例子n5 的完整过程光讲公式容易飘我拿一个具体例子走一遍。设 n 5points [(1,2),(1,4),(3,1),(4,3)]。先统计 cntcnt[0] 0cnt[1] 2两个点的横坐标都是 1cnt[2] 0cnt[3] 1cnt[4] 1cnt[5] 0total 4。求前缀和 prepre[0] 0pre[1] 0 2 2pre[2] 2 0 2pre[3] 2 1 3pre[4] 3 1 4pre[5] 4 0 4逐个枚举 k 1, 2, 3, 4kL pre[k-1]R total - pre[k]|L - R|1pre[0] 04 - pre[1] 222pre[1] 24 - pre[2] 203pre[2] 24 - pre[3] 114pre[3] 34 - pre[4] 03最小差值在 k 2 时取到答案是 0。也就是说在 x 2 的位置切一刀左边两个点、右边两个点刚好平分。3.3 代码实现Python 和 C 双版本思路理清之后代码其实短得可怜。Python 版本如下from typing import List def min_split_difference(n: int, points: List[List[int]]) - int: cnt [0] * (n 1) for x, y in points: cnt[x] 1 total len(points) # 前缀和pre[i] 表示 x i 的点数 pre [0] * (n 1) for i in range(n 1): pre[i] cnt[i] (pre[i - 1] if i 0 else 0) ans 10 ** 18 for k in range(1, n): left pre[k - 1] # x k right total - pre[k] # x k ans min(ans, abs(left - right)) return ans if ans ! 10 ** 18 else 0C 版本也不复杂习惯了用数组直接模拟class Solution { public: int minSplitDifference(int n, vectorvectorint points) { vectorint cnt(n 1, 0); for (auto p : points) { cnt[p[0]]; } int total points.size(); vectorint pre(n 1, 0); for (int i 0; i n; i) { pre[i] cnt[i] (i 0 ? pre[i - 1] : 0); } int ans INT_MAX; for (int k 1; k n; k) { int left pre[k - 1]; int right total - pre[k]; ans min(ans, abs(left - right)); } return ans INT_MAX ? 0 : ans; } };复杂度方面统计 cnt 需要遍历所有点 O(m)求前缀和和枚举 k 都是 O(n)整体时间复杂度 O(n m)额外空间是 O(n)。放在 n 和 m 都是十万级的数据范围内毫无压力。这种效率也解释了为什么最优解不需要二分整个搜索空间本来就只有 n-1 个整数位置线性扫一遍是最直接、最不可能写错的方案。3.4 边界问题为什么 k 只能取 1 到 n-1有几个边界条件值得单独拿出来说因为它们在周赛里害人无数。第一k 不能取 0 也不能取 n。k 0 时竖线与正方形左边重合根本没有分割出左右两块k n 时同理。题目要求的分割必须让左右两边都包含一部分正方形内部所以可选的 k 就是 1 到 n-1。第二当 total 0 时也就是正方形内一个点都没有那么任意分割线两侧都是 0差值为 0答案自然是 0。第三注意 pre 数组的长度是 n1循环里访问 pre[k] 时 k 最大是 n-1所以不会越界但如果把 n 理解成点的个数而不是边长就非常容易搞混。我建议做题前先看清楚题面里 n 到底是正方形的边长还是点的数量这个理解误差可以直接导致数组开错。4. 变体与进阶从分割正方形 I往后续题目想4.1 如果竖线上的点也被计入某一侧前面我采用了竖线上的点不算的口径但实际周赛里完全可能改成竖线上的点算左侧或者算右侧。这个微调对算法主体没有影响只影响 L 和 R 的表达式。如果竖线上的点算左侧L pre[k]R total - pre[k]也就是所有点都被严格分到左边或右边竖线上的点归左。这时差值就是 |2 * pre[k] - total|扫描时直接用这个式子。如果算右侧L pre[k-1]R total - pre[k-1]同理。我的建议是不要背公式而是记住一个原则先明确 cnt[k] 归哪边再让 L 和 R 的表达式覆盖所有点保证 L R total。只要这个等式成立你的统计口径就是自洽的怎么定义都是安全的。4.2 如果允许任意实数坐标的竖线这是分割正方形 II很喜欢玩的升级。竖线位置 k 不再限定为整数而是可以在 (0, n) 区间内取任意实数。此时差值函数 |L(k) - R(k)| 会变成一个关于 k 的阶梯函数只有当 k 扫过某个点的横坐标时左侧点数才会加一右侧点数才会减一其余区间内差值保持不变。处理这类问题的核心工具是区间合并和差分数组。具体思路是把所有点的横坐标排序然后枚举每一个相邻关键点之间的开区间区间内任意取 k 效果完全一样。找出差值最小的区间即可。更进一步如果存在一段区间使得 L R那就说明可以在该区间内任选一个实数位置答案是 0。这种连续化的思路在《爱吃香蕉的狒狒》LeetCode 073 那类二分答案题里面也很常见本质上都是在连续区间上找满足条件的点只是一个是二分一个是扫区间。4.3 如果改成求能达到最小差值的分割线数量还有一种常见问法不要最小值问在 1 到 n-1 中有多少个整数 k 可以让 |L - R| 等于最小值。这个改动对代码来说几乎是免费的只需要在扫描时多维护一个计数器遇到更小差值时重置为 1遇到相等差值时加一。这类最优解计数的题目在周赛 Q3 里面经常出现难度不高但考察细节很多人会在重置逻辑上漏写一个条件。我写这类题的习惯是先用一个变量维护当前最优值再用另一个变量维护达到最优值的方案数每次更新时先判断是否更优再判断是否相等顺序不能反。4.4 如果点的坐标大到不能开数组当 n 达到 10^9 级别cnt 数组长度根本开不下。这时候就要放弃按坐标开桶的思路改成排序加双指针。具体做法把所有点的 x 坐标排序从左往右扫描分割线位置维护一个指针不断把 x 小于当前 k 的点纳入 L同时用总数减去 L 和竖线上点的数量得到 R。排序 O(m log m)空间 O(m)完全避开 n 的规模。这一招在离散化问题里是必会的。数组能开下的时候用桶数组开不下的时候用排序本质都是把横坐标压缩成有序序列。很多中等题和困难题的分水岭就在这里不是算法变了而是数据结构能不能承受数据的规模。5. 周赛实盘这类题的提速技巧与常见坑5.1 读题 30 秒锁定一维化经过上面这些分析你应该发现这类题有一个非常明显的识别信号正方形、点集、平行于坐标轴的切割线、计数。只要这四要素同时出现九成是一道一维化加前缀和的题。比赛时看到这种题我会在草稿纸上快速画一个数轴把点按横坐标标上去然后问自己三个问题点是否只靠一维坐标区分切割线位置是否离散能否用前缀和表示两侧统计量三个问题回答完解法基本就定了。我特别想强调先写暴力再优化这种实战策略。如果你在比赛里一时想不出前缀和可以先写一个 O(n*m) 的暴力枚举确认题目理解正确然后再把内层循环用前缀和换掉。这个过程看起来多花了五分钟实际上比直接对着空编辑器发呆要快得多。很多时候暴力解法本身就是最好的调试工具它能帮你逼出所有边界条件。5.2 常见报错与排查实录我把这道题容易踩的坑整理成了一张速查表都是我真实犯过的错误供你参考症状可能原因解决办法数组越界把边长 n 和点数 m 搞混cnt 开小了确认变量含义cnt 长度按 n1 开答案一直偏大竖线上的点没从 total 里扣掉检查 R total - pre[k] 是否用了 pre[k]k 取 0 或 n 也算进去了没注意题目要求分割必须把正方形切开循环范围写成 range(1, n)大 n 时答案错误用 int 存累加结果溢出Python 不担心C 用 long long总点数为 0答案异常没有单独处理 total 0 的情况返回 0最小值没更新ans 初始值不够大初始化为 10^97 或 INT_MAX还有一个非常隐蔽的坑当 cnt[x] 本身很大时pre 数组的中间值可能超过 int 范围。LeetCode 的题一般会卡这个所以你哪怕只是求最小差值也建议在 C 里直接开 long long不要省这一点内存省下来的时间可以多调试两个用例。5.3 和二分答案题的内在联系可能有人会问这题能不能二分答案是能但没必要。如果题目问的不是最小值而是是否存在某个 k 使得左侧点数大于等于某一个目标值那就可以二分 k每次用 pre 数组判断当前左侧点数是否达标。这正好是 LeetCode 073《爱吃香蕉的狒狒》那类二分答案题的处理方式给定一个目标判断当前阈值是否满足条件。这两种思路的边界处理也有相似之处。二分题里最容易错的是到底是 left right 还是 left right以及中点 mid 是否可能陷入死循环。前缀和题里最容易错的是左右两侧是否覆盖了所有点。本质上它们都在考同一件基本功对离散边界的精确理解。把这道题和 073 那道题放在一起对比着做你会发现所谓的中等题套路都是相通的。最后说点题外话我个人在实际操作中的体会是LeetCode 周赛的中等题从来不靠偏题怪题取胜它赢在误导——用看起来复杂的包装掩盖一个简单的模型。3453 这道分割正方形 I就是非常标准的例子你把正方形外衣一脱里面的内容就是一个一维计数。这种题做多了之后遇到任何分割区域点集相关的题目我都会先问自己一句这个问题是不是可以降维答案一旦变成是剩下的就是把排序、前缀和、二分这些基本功拿出来稳稳地写。如果你正准备备战周赛或者刷题瓶颈期建议把这题的变体都练一遍整数竖线、实数竖线、横线分割、求数量、离散化。每多练一种变体你对这类题的理解就会深一层。刷题本来就是个拼图游戏这题可能只是你拼图里的一小块但有了它旁边几块也会跟着变得清晰。