1. 先聊聊这道题到底在考什么LeetCode 1401这道题题目描述很直白给你一个圆的圆心坐标和半径再给你一个矩形的左下角和右上角坐标判断圆和矩形是否有重叠。但题目越短陷阱越多。我第一次交的时候自信满满地写了一堆分情况讨论的if-else结果WA了三次才过。后来回头看才发现这题考的根本不是几何直觉而是如何把一个看似复杂的空间关系问题转换成一个足够简单、不容易出错的数学模型。从面试角度来说这道题属于“计算几何”里最基础的相交判断但它常见的变形会出现在游戏开发里的碰撞检测、图形学里的裁剪算法甚至机器人路径规划里的障碍物膨胀判断。所以别觉得它只是一道刷题工具题——理解了它的核心思想你以后处理“图形A和图形B是否相交”这类问题会顺手很多题目的数据范围也很友好坐标和半径都是整数绝对值不超过10^4。这意味着一个很关键的事情大部分运算可以用整数完成根本不需要碰浮点数。这点我后面会展开细说因为“能用整数就不用浮点”是这类几何题里最容易踩坑也最容易拿满分的一个优化点。2. 核心思路拆解别按直觉分区域用“最近点”写法一劳永逸2.1 从“圆和矩形重叠”翻译成数学条件很多人的第一反应是分情况圆在矩形左边、右边、上边、下边、四个角……然后每个方向单独判断圆和边的距离。这种思路没错但代码会膨胀得很厉害而且极易在“圆到底有没有压到角”这种边界上出错。我推荐换一个角度想圆和矩形重叠等价于圆心到矩形区域的最短距离小于等于圆的半径。这个“最短距离”怎么定义分两种情况如果圆心在矩形内部或者在边上距离就是0直接判重叠。如果圆心在矩形外部那最短距离就是圆心到矩形四条边所在的矩形边界的最近距离。这样一翻译问题就从“判断两个图形的相交关系”变成了“求一个点到矩形的最短距离”后面这个在数学上是有闭式解的。而闭式解对应的代码非常干净不需要写一堆if-else嵌套。2.2 把矩形“压”到第一象限思路瞬间清晰这里有个使用频率极高的技巧做坐标变换把矩形中心平移到原点再利用矩形的对称性把问题“折叠”到第一象限。具体来说矩形可以用它的半宽和半高来描述。假设矩形的左下角是(x1, y1)右上角是(x2, y2)那么中心点cx0 (x1 x2) / 2中心点cy0 (y1 y2) / 2半宽hx (x2 - x1) / 2半高hy (y2 - y1) / 2然后把圆心也做相对平移得到相对于矩形中心的坐标(dx, dy) (x - cx0, y - cy0)。这时候因为我们只关心“到矩形的最短距离”而矩形关于中心点是中心对称的所以可以直接取dx和dy的绝对值或者说把圆心按对称关系映射到第一象限。映射完之后的问题就极其简单了第一象限里有一个以原点为中心的矩形它的范围是[0, hx] × [0, hy]圆心变成了第一象限里的某个点(|dx|, |dy|)求这个点到这个矩形的最短距离。2.3 关键步骤把圆心“夹”到矩形边界上现在到了最核心的一步。我们有了第一象限的矩形[0, hx] × [0, hy]以及点(|dx|, |dy|)。怎么求点到矩形的最短距离答案就是一句话把这个点“投影”到矩形内部最近的点上。具体操作是三个clamp钳位操作closestX min(max(|dx|, 0), hx)closestY min(max(|dy|, 0), hy)换句话说如果|dx|在0到hx之间那最近点的x坐标就是|dx|本身如果|dx|大于hx最近点的x坐标就是hx如果|dx|小于0最近点的x坐标就是0。y方向同理。然后求这个最近点(const closestX, closestY)到圆心(|dx|, |dy|)的距离的平方distSq (|dx| - closestX)^2 (|dy| - closestY)^2最后比较distSq和r^2。若distSq r^2说明圆和矩形重叠。这个思路最优雅的地方在于不管是圆心在矩形内部、外部、还是正好在边界上这三行clamp逻辑全部覆盖了不需要任何额外的分支。提示为什么用平方距离而不是直接算距离因为平方距离可以完全避免开根号操作既省时间又避免浮点误差。在范围只有10^4的情况下平方后的最大值是(2×10^4)^2 (2×10^4)^2 8×10^8用long long完全不会溢出。这是我推荐的第一优先级写法。3. 两种主流解法的实现与对比3.1 解法一坐标变换 最近点法推荐代码极短先给出我最推荐的实现。这个方案把中心对称、取绝对值、clamp三步走完代码短到让人怀疑是不是漏了什么。以C为例class Solution { public: bool checkOverlap(int radius, int xCenter, int yCenter, int x1, int y1, int x2, int y2) { // 矩形中心 double cx (x1 x2) / 2.0; double cy (y1 y2) / 2.0; // 半宽半高 double hx (x2 - x1) / 2.0; double hy (y2 - y1) / 2.0; // 圆心相对矩形中心的坐标取绝对值映射到第一象限 double dx fabs(xCenter - cx); double dy fabs(yCenter - cy); // 第一象限矩形范围是[0, hx] × [0, hy] // 把(dx, dy)钳位到矩形边界内部最近点 double closestX min(max(dx, 0.0), hx); double closestY min(max(dy, 0.0), hy); // 求最近点与圆心的距离平方 double distSq (dx - closestX) * (dx - closestX) (dy - closestY) * (dy - closestY); return distSq (double)radius * radius; } };这段代码的直观理解先把矩形“压缩”成一个位于原点的对称图形再利用对称性把问题限制到第一象限。此时矩形退化成一条从原点出发的“L形”边界但我们依然用clamp的方式求最近点逻辑完全一致。注意这里我使用了double因为坐标是整数但中心可能是.5。如果你不想让代码里出现浮点数可以把所有坐标都乘2用整数运算后面给方案二详细说明。3.2 解法二分区域讨论法适合理解但代码冗余另一种常见思路是直接把平面分成九个区域矩形内部、四条边的外侧、四个角的外侧。这种思路符合直觉适合用来向别人解释“为什么最近点法是对的”但写代码时分支多容易漏边界。大致框架是这样的bool checkOverlap(int radius, int xCenter, int yCenter, int x1, int y1, int x2, int y2) { // 圆心在矩形内部 if (xCenter x1 xCenter x2 yCenter y1 yCenter y2) return true; // 圆在矩形左右两侧 if (xCenter x1) { // 需要判断圆是否碰到左边这条边同时还要考虑角上的情况 } // ... }你可以想象这个写法需要处理的边界非常多。中心区域的判断还好四个角上尤其容易出错到底该用点到角点的距离还是用点到边的距离很多初学者写着写着就乱了。所以我的建议很明确**如果你只是为了解题解法一永远是第一选择。**它的代码量只有分区域法的一半而且本质上更接近“计算几何”这个领域的通用思维——只要你能把任意形状之间的关系转化成“点到区域的最短距离”问题代码就会很简单。3.3 整数运算技巧完全避开浮点数的终极写法前面提到坐标和半径都是整数这给了我们一个很大的优化空间通过把坐标乘以2可以完全避开浮点数。具体做法是在坐标变换时不除以2而是把圆心坐标也乘以2然后所有距离判断都用整数完成。class Solution { public: bool checkOverlap(int radius, int xCenter, int yCenter, int x1, int y1, int x2, int y2) { // 所有坐标乘以2避免浮点 long long r2 4LL * radius * radius; // 半径也乘2所以平方后是4倍 long long cx 1LL * (x1 x2); // 矩形中心×2 long long cy 1LL * (y1 y2); // 矩形中心×2 long long hx 1LL * (x2 - x1); // 矩形半宽×2 long long hy 1LL * (y2 - y1); // 矩形半高×2 long long dx llabs(2LL * xCenter - cx); long long dy llabs(2LL * yCenter - cy); // clamp long long closestX min(max(dx, 0LL), hx); long long closestY min(max(dy, 0LL), hy); long long distSq (dx - closestX) * (dx - closestX) (dy - closestY) * (dy - closestY); return distSq r2; } };这个写法的好处是完全避开了浮点运算彻底不存在精度问题。而且因为坐标范围很小中间的乘法结果最大也就8×10^8long long绰绰有余。实操心得我实际测下来这个整数版本和浮点版本的耗时几乎没有差别LeetCode这题的数据量太小性能差异测不出来但整数版本让人心里更踏实——毕竟浮点比较里distSq r^2这种判断如果数值恰好相等浮点误差可能让你多一次WA。整数写法直接消灭了这类不确定因素。3.4 两种方案如何选场景决定一切如果你在面试中遇到这题我建议先讲思路时用分区域法因为面试官容易理解你的几何直觉但真正写代码时直接上最近点法边写边解释“这个写法统一了所有分支”。这样既展示了你能从几何角度理解问题又展示了你能把数学结论转化为简洁代码的能力。如果你只是自己刷题那答案更简单直接记住最近点法。它的代码量最小出错的概率最低而且更容易迁移到其他题型上——比如求圆和三角形、圆和多边形是否重叠思路都是“求点到区域的最短距离”。4. 复杂度分析与性能表现4.1 时间与空间复杂度这道题的时间复杂度是O(1)因为我只做了有限的几次加减乘除和比较操作与输入数据的大小无关。空间复杂度同样是O(1)只用了几个临时变量。复杂度虽然简单但在解题报告里一定要写清楚尤其是要说明“为什么是O(1)而不是O(n)”——因为这里没有任何遍历操作数据规模是固定的输入参数圆心坐标、半径、矩形坐标算法只处理这些常量个数的数值。4.2 “耗时100”是怎么做到的LeetCode显示“耗时100%”的提交通常意味着代码运行时间进入了所有提交里的第一梯队。想做到这一点代码本身要避免不必要的库函数调用和动态内存分配当然更重要的是算法层面没有浪费操作。我的整数版最终耗时确实能稳定排在100%但说实话这题的测试规模下算法思想才是第一位常数优化空间很小。真正让你“耗时100%”的不是某个魔法操作而是你选择了一个根本没有多余操作的写法不算开方、不调三角函数、不创建额外数据结构、不写一堆无意义的中间变量。实操心得如果你在LeetCode上看到耗时排名不是100%也别太纠结。本地测评机器负载波动、并发提交时间差都会影响百分比。我更看重的是“代码无浮点、无分支冗余、无重复计算”这三点做到这些排名自然差不到哪去。5. 边界条件与易错点盘点5.1 圆和矩形“刚刚相切”算不算重叠这是这题最微妙的地方。按照题目的定义相切算重叠因为重叠的定义是“有公共点”而相切恰好有一个公共点。所以判断条件必须是distSq r^2而不是distSq r^2。这个细节我在第一次提交时就踩坑了我以为相切不算写了严格小于结果样例过不了。后来查题解才发现题目的判定标准是“圆和矩形是否有重叠”只要有一个点接触就算重叠。这个边界条件必须记住面试时也经常被问到“相切你怎么处理”。5.2 圆心恰好等于矩形中心点当圆心和矩形中心完全重合时dx 0dy 0closestX 0closestY 0distSq 0。这时候只要半径0半径肯定是正数直接判重叠。这个case在最近点法里被统一处理了不需要额外分支。如果你用的是分区域法这里也还好因为圆心在矩形内部会直接返回true。但如果你写的是“至少距离某条边小于半径”这种判断就要小心圆心在矩形内部时离四条边最近的距离也可能是0必须和“圆心在矩形外部”的分支区分开稍微不注意就漏了。5.3 圆心恰好在矩形边上如果圆心在矩形边上比如恰好xCenter x1且yCenter在y1和y2之间那dx或dy就会等于hx或hyclamp之后距离是0直接判重叠。这也是“圆心在矩形内部或边上就直接重叠”的情形最近点法统一处理不需要额外写“是否在边上”的判断。5.4 防止溢出的细节虽然题目给的范围是10^4但在计算distSq时如果直接用int存dx - closestX的结果再相乘可能在某些变体题目里溢出比如坐标范围扩大。我的建议是任何涉及平方运算的变量都声明为long long这是成本最低的防御性编程。我实测过哪怕不乘2直接硬算保持double版本也不会溢出但long long版本没有任何坏处反而让代码更统一。6. 常见问题排查与调试技巧6.1 我的结果是WA但看起来逻辑没错出现这种情况时我一般会把圆心坐标、矩形坐标直接打印出来自己用草稿纸画个图。常见的原因有三个一是相切时用了而不是二是分区域法漏掉了某个角上的情况三是浮点数比较时用了而不是。针对调试我建议把每个case的dx、dy、closestX、closestY都打印出来手动算一遍距离平方然后跟代码结果对比。你会发现大部分WA都是某个坐标在边界值时clamp的结果和你预期的不一致。6.2 我用了浮点数但总觉得不稳浮点误差在几何题里确实是个隐患。最经典的翻车场景是理论上应该相切的两个图形因为浮点误差算出距离平方等于 r^2 1e-9然后被判定为不重叠。规避方法就是前面说过的整型化。把所有坐标乘2所有运算都在整数域内做。如果你不想改代码也可以把比较条件改成distSq r^2 1e-9但我觉得这种“加epsilon”的写法治标不治本不如直接整型化来得干净。6.3 我不理解为什么要取绝对值很多新手会卡在这一步。我换个方式解释矩形是关于中心点对称的所以圆心在矩形的左上角、右上角、左下角、右下角本质上到矩形的距离是完全一样的。取绝对值就是把这四个角的情况全部“折叠”到右上角这一种情况来处理。打比方说你在教室里问“我离讲台最近的距离是多少”无论你站在讲台的哪一侧答案都等于“你站在第一象限的同学到讲台的距离”——因为教室是对称的。取绝对值就是把这个对称性利用到极致让代码少写四分之三的分支。6.4 如何验证我的代码是对的除了提交LeetCode看判定结果我强烈建议你多构造一些手写测试用例。比如圆完全在矩形内部应该返回true圆完全在矩形外部且距离很远应该返回false圆和矩形相切应该返回true圆非常大覆盖了整个矩形应该返回true圆心在矩形角点正上方半径很小应该返回false我在本地用这五个case验证基本能覆盖大部分逻辑错误。你甚至可以把分区域法和最近点法两个版本都写上随机生成坐标对拍确认两个版本输出一致——这是竞赛选手常用的“对拍策略”非常管用。7. 从这题出发下一步你可以怎么练7.1 相关题目的延伸脉络做完1401之后我建议你顺着两个方向继续练第一个方向是“点到图形的最短距离”比如求点到线段的最短距离、点到三角形的最短距离。LeetCode上没有太多直接考察这点的题但面试里常以“求一个点到多边形内部的距离”这类变形出现思路完全相同核心就是找到所有可能的最近点候选然后取最小距离。第二个方向是“图形相交判断”比如让你判断两个矩形是否重叠、两个圆是否重叠、圆和三角形是否重叠。这些题都能归约到“距离比较”上来你只要把一个图形上的点集合、另一个图形上的点集合之间的最小距离求出来和某个阈值比较即可。7.2 把这道题的思维用到工程里我在实际项目里遇到过和这个题几乎一模一样的场景有一个圆形传感器需要判断它扫过的区域是否碰到了某个矩形的障碍物。当时的代码就是把“圆心到矩形的最短距离”这个函数独立出来供多个模块复用。后来团队做碰撞检测优化这个函数成了核心模块之一。所以别小看这个看似简单的题它背后的“距离场”distance field思想在图形学、机器人、游戏AI里都是基础。理解了最近点你就理解了“如何把一个几何问题变成数值问题”这条思路能解决很多看起来无从下手的几何问题。7.3 刷题先后顺序的参考如果你是按LeetCode热门100题的顺序刷遇到这种计算几何题时可以先跳过把重点放在字符串、树、动态规划上。但如果你的目标是面试中的“系统设计 算法”双轮考核这种几何题反而是容易拿分的点——因为套路固定、代码量小、不容易出错而且面试官一看到你用最近点法而不是分区域法会觉得你对计算几何有真实的理解。我个人建议的顺序是先刷完数组、链表、二叉树这类基础题给自己建立信心然后再集中攻克几何题。1401作为几何题的入门性价比非常高值得花半小时彻底搞懂。7.4 最后分享一个我踩过的坑这题我第一次提交时写了分区域法自测全过兴冲冲提交结果WA。查了很久发现问题出在“圆心在矩形左边且半径足够大碰到矩形左上角”这个case上——我的代码只判断了圆心到左边这条垂直线段的距离忘了判断到左上角这个角点的距离。这个错误特别隐蔽因为大多数自测用例都不会精确构造“圆在角的外侧但刚好碰到角”的情况。后来用最近点法重写这个bug就不存在了因为clamp操作天然把角点的判断统一进去了。这个经历让我彻底改变了对待几何题的习惯能用数学归结法解决的问题绝不用几何分支法。分支越多越容易漏归结成公式代码短逻辑也更容易被验证。希望你也能从这个教训里受益。