前两天在群里看到有人问“最小循环子数组”我先是一愣——环形数组的最大子数组和已经是LeetCode 918那道经典题了怎么还有人问最小版本后来想想也合理大多数人刷题都习惯从“最大”入手最小版本虽然完全对称但真到了面试里反而更容易暴露对跨边界子数组理解不到位的问题。我按最常见的问题定义来聊给定一个首尾相接的循环数组比如nums [1, 2, -3, 4, -2]最后一个元素-2和第一个元素1也算相邻要求找出所有非空连续子数组中和最小的一个。正常解法用Kadane算法的变体做一次遍历就能搞定真正难的不是代码本身而是“跨边界那部分子数组到底怎么转换”这一层理解。这篇文章会把推导过程、边界条件、暴力验证方法和面试讲述思路一起过一遍适合正在刷算法题准备面试的人也适合想搞懂动态规划和环形数组本质的人。如果你只想要一份能直接抄的代码可以直接跳到第4节但我建议你还是把第3节的推导看一遍因为面试官问的不是代码是思路。1. 先搞清楚“最小循环子数组”到底在问什么1.1 循环数组和普通数组差在哪普通数组的子数组就是一段连续区间例如nums[i..j]起点和终点都老老实实落在原数组的范围内。循环数组则不一样物理上数组还是那个数组但逻辑上它的末尾和开头接上了形成了一个环。于是子数组多了一种形态从数组后半段出发跨过末尾再绕回数组开头接着走。比如nums [1, 2, -3, 4, -2]子数组[-2, 1]在线性视角下是两个不相邻的元素但在循环视角下它们就是相邻的因为-2是最后一个元素1是第一个元素环上它们紧挨着。我习惯用一个通俗的类比把数组想象成一条环形跑道子数组就是沿着跑道跑一段连续的路程。普通数组相当于跑道上有一堵墙你只能从某个起点跑到某个终点循环数组则把这堵墙拆了你可以跨过“终点线”继续跑只要不回头、不重复踩同一个位置就行。这个“不重复踩同一个位置”很重要环上连续子数组的长度最大只能是n不能超过一圈否则就会包含重复元素。这一点看起来简单却经常有人在用“破环成链”方法时犯错后面我会专门讲。1.2 输入输出和几种等价表述明确一下输入输出输入整数数组nums长度n 1元素可正可负可为零。输出所有非空连续子数组的最小和。如果需要还可以输出对应的起始和结束下标。这道题和几个常见表述是等价的求环形数组中的最小连续子段和。求循环数组上长度不超过n的连续子数组的最小和。求数组nums nums双倍数组中所有长度在1..n之间的子数组的最小和。第三种表述尤其重要它直接引出了最直观的暴力解法也方便后面做随机验证。举个稍微复杂的例子nums [-2, 3, -2, 3, -2]。普通连续子数组的最小和是多少单个-2答案是-2。但如果把数组首尾接起来子数组可以取最后一个-2和第一个-2拼接成的[-2, -2]它们在环上相邻和是-4。所以整个循环数组的最小子数组和是-4而不是-2。这个例子能帮我们发现一个关键现象最优答案不一定落在“线性的连续区间”里它可能跨越边界。这也就是为什么不能只套一个普通的最小子数组算法就收工。2. 暴力解法的思路和它的天花板2.1 破环成链最直觉的做法很多人第一次看到环形数组第一反应都是“把它变成一条直线”。具体做法是把数组复制一遍拼在后面得到长度2n的双倍数组double_nums。例如nums [-2, 3, -2, 3, -2]双倍数组就是[-2, 3, -2, 3, -2, -2, 3, -2, 3, -2]为什么要复制因为任意一个跨边界的循环子数组比如原数组的[nums[4], nums[0]]在双倍数组里都能被表示为一段普通的连续子数组[double[4], double[5]]。这样一来环形问题被简化成了普通的一维数组问题。但在枚举时有一个大坑双倍数组里能取到的子数组长度不能随便取。由于环上子数组最多包含n个元素枚举时长度范围必须限制在[1, n]。如果直接枚举双倍数组里的所有连续子数组会把长度超过n的、包含了重复元素的区间也算进去得到错误结果。2.2 两层循环加前缀和的复杂度分析暴力实现的核心就是枚举所有起点和所有合法长度。用前缀和优化累加过程后可以写成下面这样def brute_min_circular(nums): n len(nums) if n 0: raise ValueError(数组不能为空) doubled nums nums # 构造前缀和方便 O(1) 求任意区间和 prefix [0] * (2 * n 1) for i in range(2 * n): prefix[i 1] prefix[i] doubled[i] best float(inf) for start in range(n): # 只枚举原数组起点避免重复 for length in range(1, n 1): # 长度最大为 n s prefix[start length] - prefix[start] if s best: best s return best起点只需要枚举0..n-1就够了因为环上的任意起点都能映射到双倍数组的这前n个位置之一长度限制在1..n保证子数组不会绕超过一圈。复杂度是O(n^2)空间O(n)。对n 1000的测试数据完全够用但题目规模一旦到10^5甚至10^6这个方案就彻底不行了。不过别急着扔掉它。暴力解法的真正价值在于它逻辑简单、不容易出错可以作为验证线性解法的基准答案。我后面做随机测试时全靠它来检查正确性。这也是我强烈建议的方法——写优化解法之前先写一个笨办法来兜底能省下大量调Bug的时间。暴力法看完了接下来进入正题怎么把复杂度降到O(n)。3. 从Kadane算法出发的线性解法推导3.1 先写一个求最小子数组和的最小Kadane普通数组的最小连续子数组和是经典Kadane算法的镜像版本。最大子数组的Kadane维护的是“以当前位置结尾的最大和”最小子数组则维护“以当前位置结尾的最小和”。定义一下设dp[i]表示以nums[i]结尾的连续子数组的最小和。那么有两种情况直接从nums[i]开始不接前面的部分此时dp[i] nums[i]。接上前面的一段此时dp[i] dp[i-1] nums[i]。取两者中的较小值即可dp[i] min(nums[i], dp[i-1] nums[i])最终答案就是所有dp[i]的最小值。这个递推式的正确性依赖一个直觉如果“以i-1结尾的最小和”是一个负数那接上它通常会让当前结果更小如果它是正数那就干脆丢掉前缀从当前元素重新开始。这和贪心不太一样本质是动态规划的状态转移。代码可以压缩成一次遍历def min_subarray(nums): cur_min nums[0] min_sum nums[0] for x in nums[1:]: cur_min min(x, cur_min x) min_sum min(min_sum, cur_min) return min_sum对[-2, 3, -2, 3, -2]跑一遍得到的min_sum -2和前面分析的一致普通线性数组的最小连续子数组就是单个-2。3.2 跨边界子数组的关键转换总和减最大子数组现在问题来了什么时候最优子数组会跨过边界跨边界的子数组在线性表示下的形状是“后半段的一个后缀 前半段的一个前缀”。举个例子nums [a, b, c, d, e]跨边界子数组可能是[d, e, a, b]。你发现规律没有如果从整个数组里“挖掉”跨边界子数组剩下的部分是一个中间连续段[c]。反过来看跨边界子数组其实就是“全集减去一个中间连续段”。要让跨边界子数组的和最小等价于让被挖掉的中间连续段的和最大。中间连续段就是普通数组的某个连续子数组它的最大和刚好可以用最大Kadane算法求出。于是就有了这个经典的转换跨边界最小子数组和候选值 total - max_sum其中total是数组总和max_sum是普通线性数组的最大连续子数组和。为什么这个等式成立设跨边界子数组为C它的补集被挖掉的中间段为M。显然C total - M。要让C最小就要让M最大。而M的取值范围就是所有“非空、且不是全集”的连续子数组。最大的那个M正好就是max_sum。这里有两个细节需要立刻敲警钟M不能是空集。空集意味着跨边界子数组是全集而全集在线性表示下并不跨边界而且枚举它没有意义。全非负数的数组会出现这种情况。M不能是全集。全集意味着跨边界子数组是空集题目不允许空子数组所以这个候选直接作废。这两个细节会在第4节的代码里体现为边界判断。3.3 完整公式和数学证明综合上面两类情况答案可以写成answer min(min_sum, total - max_sum)在不触发边界陷阱的前提下前面加一个条件if max_sum total: answer min_sum else: answer min(min_sum, total - max_sum)其中min_sum普通线性数组的最小连续子数组和覆盖“不跨边界”的情况。total - max_sum覆盖“跨边界”的情况。为什么max_sum total时要单独处理因为如果最大子数组和等于总和说明最大子数组把整个数组都包含进去了。此时被挖掉的M是全集跨边界候选total - max_sum 0对应的是一个“空子数组”不能要。什么数组会出现这种局面所有元素都是非负数的时候比如[1, 2, 3]或[0, 1, 2]。这种情况下的最小循环子数组就是普通最小子数组也就是最小的那个元素或最靠前的0之类的单元素子数组。反过来如果数组里存在负数最大子数组和必然严格小于总和total - max_sum才是一个真实存在的非空跨边界子数组可以放心参与比较。4. 代码实现与边界情况处理4.1 Python核心实现一次遍历同时维护四个变量最小子数组、最大子数组。下面是完整的Python实现关键地方我都写了注释。def min_sum_circular(nums): if not nums: raise ValueError(数组不能为空) total sum(nums) # 初始化不允许空子数组所以都用 nums[0] 开局 cur_min nums[0] min_sum nums[0] cur_max nums[0] max_sum nums[0] for x in nums[1:]: # 最小子数组 Kadane cur_min min(x, cur_min x) min_sum min(min_sum, cur_min) # 最大子数组 Kadane cur_max max(x, cur_max x) max_sum max(max_sum, cur_max) # 如果最短的“挖掉段”把整个数组都挖掉了说明不存在合法的跨边界候选 if max_sum total: return min_sum return min(min_sum, total - max_sum)这里有两个初始化细节值得展开说。第一cur_min不能初始化为0。标准Kadane求最大子数组时很多教程为了处理空数组会把初始值设为0允许“选择空子数组”。但本题要求非空如果全正数组[1, 2, 3]走了这种初始化min_sum会被算成0答案错误地变成0。正确做法是用nums[0]初始化然后在循环里从nums[1]开始迭代。第二cur_max同理不能用0初始化。一个很隐蔽的Bug是如果数组全为负数max_sum如果被错误初始化为0那么total - max_sum会比真实值偏小导致答案错误。必须用nums[0]作为起点。4.2 全正数、全负数、单元素这三类边界我把最容易出错的边界情况放在一起用代码逐一验证数组totalmin_summax_sumtotal - max_sum最终答案正确答案[1, 2, 3]6160空子数组非法11[-1, -2, -3]-6-6-1-5-6-6[7]7770非法77[-2, 3, -2, 3, -2]0-24-4-4-4逐个解释一下。第一行[1, 2, 3]全正max_sum total直接返回min_sum 1。环上确实可以选[3, 1]或[2, 3]但它们的和都比1大最优就是单个1。第二行[-1, -2, -3]全负min_sum会算成整个数组的和-6。很多人直觉以为最小子数组应该是最小的那个负数也就是-3但在允许连续取多个负数的情况下[-1, -2, -3]全部取完才是最小所以答案是-6。这个反直觉点很重要。第三行[7]单元素max_sum total成立走return min_sum分支返回7。如果没有这个分支保护min(7, 7-7)会得到0直接翻车。第四行展示的是真正的跨边界最优解。min_sum -2但total - max_sum 0 - 4 -4后者更小。对应的子数组是[-2(最后一个), -2(第一个)]它们跨过了边界在普通线性视角下不相邻但在环上确实是连续的。4.3 不止一种写法一次遍历同时维护四个变量前面代码里最小和最大Kadane是在同一个循环里完成的这样只需要遍历一次数组空间复杂度O(1)。如果你觉得同时维护四个变量容易绕晕也可以拆成两个循环分别求min_sum和max_sum思路更清晰def min_sum_circular_simple(nums): total sum(nums) def min_kadane(arr): cur arr[0] best arr[0] for x in arr[1:]: cur min(x, cur x) best min(best, cur) return best def max_kadane(arr): cur arr[0] best arr[0] for x in arr[1:]: cur max(x, cur x) best max(best, cur) return best min_sum min_kadane(nums) max_sum max_kadane(nums) if max_sum total: return min_sum return min(min_sum, total - max_sum)两段代码逻辑完全等价。拆开的好处是容易调试坏处是遍历两次。面试时你可以先写拆开的版本讲清楚思路再提一句“实际可以合并成一次遍历”会比一上来就甩出一个四变量版本更容易让人听懂。5. 实测验证与踩坑复盘5.1 用随机测试验证公式的正确性线性解法的推导听起来很顺但你敢不敢保证它一定对我的习惯是写一个暴力解法作为基准然后生成大量随机小数组做对比。只要样本够多边界情况再隐蔽也能被揪出来。下面这段代码就是干这件事的import random def brute_min_circular(nums): n len(nums) doubled nums nums prefix [0] * (2 * n 1) for i in range(2 * n): prefix[i 1] prefix[i] doubled[i] best float(inf) for start in range(n): for length in range(1, n 1): s prefix[start length] - prefix[start] if s best: best s return best def run_random_test(times10000, n_max10, value_range10): for _ in range(times): n random.randint(1, n_max) nums [random.randint(-value_range, value_range) for _ in range(n)] a brute_min_circular(nums) b min_sum_circular(nums) if a ! b: print(验证失败:, nums, 暴力结果:, a, 线性结果:, b) return False print(f随机测试 {times} 组全部通过) return True run_random_test()这组测试覆盖了长度为1的小数组、全正数、全负数、大量零、正负混杂等各种情况尤其是元素范围在-10..10时数组里很容易同时出现正数和负数跨边界分支会被频繁触发验证价值很高。我实际跑过很多次这个公式能稳定通过测试。但测试通过不代表你可以忽略边界分支因为测试数据里偶然没有触发max_sum total的情况也不奇怪。真正确认边界逻辑还得靠针对性的用例比如[1, 2, 3]和[7]。5.2 我踩过的两个坑空子数组与max_sum等于total第一个坑是空子数组问题。我最早写最小Kadane时偷懒把cur_min初始化为0想着反正后面会更新。结果拿[1, 2, 3]一测试返回0。当时还纳闷了半天明明所有元素都是正数最小子数组怎么可能是空的和0后来才意识到空子数组在动态规划里被默认允许了。解决办法就是固定用nums[0]初始化不允许“从空组开始选”这条路径。第二个坑是max_sum等于total时不加保护。这个更隐蔽。我不加if max_sum total直接跑全正数组得到min(1, 6-6) 0又错了一回。仔细一分析才想明白total - max_sum在数学上等于0不代表存在合法的空子数组而是代表“跨边界候选对应的补集是全集”这个候选必须被丢弃。这两个坑互为镜像一个是动态规划状态初始化允许了空段另一个是推导公式时允许了空子数组作为答案。本质都是同一个原因——没有严格执行“子数组非空”这个题目约束。5.3 面试中怎么讲这道题更容易加分代码谁都会背面试官想听的是你怎么从暴力解法过渡到线性解法。我建议按这个顺序讲先讲暴力。提到破环成链、长度限制为n、复杂度O(n^2)一句话带过面试官知道你没忘本就行。再讲线性最小Kadane。要说清楚状态转移dp[i] min(nums[i], dp[i-1] nums[i])的含义尤其是“为什么负数前缀值得接、正数前缀不值得接”。然后重点讲跨边界候选。这是最容易拉开差距的地方。可以用这句话开头“一个跨边界的子数组等价于整个数组去掉一个中间连续段。想让子数组和最小就是要让被去掉的中间段和最大。中间段的最大和就是max_sum所以跨边界候选是total - max_sum。”最后一定要主动提边界条件。“需要注意如果数组所有元素都是非负数最大子数组和会等于总和此时total - max_sum对应空子数组必须丢弃直接返回min_sum。”把这句话说出来面试官基本就能确定你是真懂而不是背答案。6. 这类题背后的通用思维环形问题的一次性解法6.1 环形数组最大子数组和是同一枚硬币的另一面其实上面这套思路稍微反转就是环形数组最大子数组和的解法也就是LeetCode 918的原题。对于最大循环子数组也有两类情况不跨边界的最大子数组直接用max_sum。跨边界的最大子数组等价于“总和减去一个中间最小连续段”候选值是total - min_sum。最终的答案就是max(max_sum, total - min_sum)注意这里的min_sum同样不能是空子数组。如果min_sum total说明所有元素非正total - min_sum对应空子数组非法直接返回max_sum。你看最大和最小完全对称。你如果掌握了“跨边界候选 全集 - 内部最优段”这个模型两道题其实就是在同一个框架里来回切换。6.2 从“求最值”到“求具体子数组”的扩展有时候题目不满足于只求最小和还要求输出具体的子数组起点和终点。这时候需要额外记录Kadane过程中的起止下标。以最小子数组为例在更新cur_min的时候如果新值是x从当前位置重新开始那么临时起点就是i如果新值是cur_min x起点保持不变。最终答案的min_sum更新时同步保存起点和终点即可。对于跨边界的候选total - max_sum事情稍微有意思一点这个候选本身没有起止点它是挖掉最大子数组后剩下的补集。所以你要先记录max_sum对应的区间[L, R]然后跨边界子数组就是终点到数组末尾的一截 数组开头到起点的一截在代码里体现为如果采用跨边界候选则返回的区间是[R1, n-1]和[0, L-1]的拼接。当然最省事的做法还是用双倍数组和滑动窗口同步推各有优缺点看题目要求。6.3 加约束的变体长度限制与前缀和单调队列如果题目改成“环形数组中长度不超过k的最小连续子数组和”Kadane就失效了因为你不知道当前段长有没有超限。这时可以用“前缀和 单调队列”解决。思路是双倍数组上维护前缀和prefix问题变成找一对i j且j - i k使得prefix[j] - prefix[i]最小。为了让这个差值最小需要在线维护滑动窗口内最小的prefix[i]这就是单调队列的标准应用。这类变体在面试里不太常见但在笔试和竞赛里出现频率不低。建议你把基础公式吃透之后再花半小时把这个滑动窗口版本写一遍对“环形数组双倍化”的理解会更上一层楼。最后分享一点个人体会环形数组相关的题最怕的不是不会写Kadane而是没意识到“跨边界子数组 全集减去中间一段”这个补集关系。想通这一点最大和最小、前缀和后缀、环形和一维本质都是同一个模型。我每次写这类题都会顺手写一个暴力验证函数多花两分钟能省下不止半小时的Debug时间。如果你有更好的解法或者踩到过别的坑欢迎在评论区一起聊聊。