1. 从一道“数组划分”题说起：为什么它值得反复琢磨
算法题里有一类题目，看起来条件简单到让人怀疑是不是漏了什么，但真正动手写的时候，才发现边界情况多到让人头皮发麻。“数组划分”就是这类题目的典型代表。题目描述通常只有一句话：给定一个整数数组和一个整数k，把数组划分成左右两部分，使得左边所有元素都小于k，右边所有元素都大于等于k，返回划分后的位置索引。没有要求排序，没有要求稳定，甚至没有要求左右两部分内部有序——听起来是不是特别简单？
但恰恰是这种“简单”的题目，最能检验一个人对双指针、原地操作、边界处理的理解深度。我在带新人的时候特别喜欢拿这道题当试金石，因为它能在十分钟内暴露出一个人的编码习惯：有人上来就开新数组，有人写双指针但边界一团糟，有人能一遍过但完全没考虑空数组和全满足的情况。这篇文章我会把这道题从思路到实现到踩坑完整拆一遍，不管你是刚刷题的新手还是想复习双指针的老手，应该都能从中找到一些之前忽略的细节。
这道题的核心价值不在于它本身有多难，而在于它是一类“原地划分”问题的模板。快速排序的partition步骤、荷兰国旗问题的简化版、甚至某些数据清洗场景中的分类操作，底层思路都跟它一脉相承。你把这题吃透了，后面遇到“把奇数放左边偶数放右边”“把负数放左边正数放右边”“把满足某条件的放左边”这类变体，基本就是换个判断条件的事。
提示：这道题在多个在线判题平台上都有收录，题号可能不同，但核心描述一致。本文的解法不依赖特定平台，任何支持基础数组操作的编程语言都可以直接套用。
2. 题目核心需求拆解与常见误区
2.1 题目到底在要求什么
先把题目用最直白的话翻译一遍。你有一个数组，比如[3, 2, 2, 1, 5, 6, 7, 4]，再给你一个目标值k，比如4。你需要把数组重新排列，让所有小于4的元素都跑到数组左边，所有大于等于4的元素都跑到右边。最终数组长什么样不重要，重要的是“分界线”在哪里——也就是第一个大于等于k的元素的位置索引。
拿上面的例子来说，划分后可能变成[3, 2, 2, 1, 5, 6, 7, 4]，此时索引4的位置是5，大于等于4，左边[3,2,2,1]全部小于4，所以返回4。也可能变成[1, 2, 2, 3, 4, 7, 6, 5]，此时索引4的位置是4，同样满足条件，返回4。注意，两种划分都合法，题目不要求唯一答案。
这里有一个容易被忽略的点：返回的索引是“第一个大于等于k的元素的位置”，也就是说这个索引左边的所有元素都严格小于k，这个索引及其右边的所有元素都大于等于k。如果数组中所有元素都小于k，那应该返回数组长度；如果所有元素都大于等于k，应该返回0。
2.2 新手最容易踩的三个坑
第一个坑是试图排序。很多人一看“左边小右边大”，下意识就想排序。排序当然能满足条件，但时间复杂度从O(n)直接飙到O(n log n)，而且完全没必要。面试中如果写出排序解法，面试官大概率会让你优化。
第二个坑是开新数组。用两个额外数组分别存小于k和大于等于k的元素，然后拼起来，这确实能过，但空间复杂度是O(n)。题目通常会有“原地划分”的隐含要求，即使没有明说，面试官也会追问能不能不用额外空间。
第三个坑是边界处理。空数组返回什么？只有一个元素返回什么？所有元素都相等且等于k返回什么？这些情况如果不提前想清楚，代码跑起来就会各种越界或者死循环。
注意：虽然题目没有明确要求“原地”，但在实际面试和工程场景中，原地操作是这类问题的默认期望。养成原地操作的习惯，对后续学习快速排序等算法也有直接帮助。
3. 双指针解法的完整推导与实现
3.1 为什么双指针是这道题的最优解
双指针的核心思想是：用两个指针从数组两端向中间靠拢，左指针找“不该在左边”的元素（即大于等于k的），右指针找“不该在右边”的元素（即小于k的），找到一对就交换，直到两个指针相遇。这样每个元素最多被访问一次，时间复杂度O(n)，空间复杂度O(1)，完美符合题目要求。
这个思路之所以高效，是因为它利用了划分问题的一个关键性质：我们不需要知道每个元素最终的具体位置，只需要保证“左边的都小于k，右边的都大于等于k”。交换操作直接把两个错位的元素一次性归位，比逐个移动高效得多。
我用一个具体例子来演示这个过程。数组[3, 2, 2, 1, 5, 6, 7, 4]，k=4：
初始状态：left=0，right=7。
- left指向3，小于4，合法，left右移到1。
- left指向2，小于4，合法，left右移到2。
- left指向2，小于4，合法，left右移到3。
- left指向1，小于4，合法，left右移到4。
- left指向5，大于等于4，不合法，停住。
- right指向4，大于等于4，合法，right左移到6。
- right指向7，大于等于4，合法，right左移到5。
- right指向6，大于等于4，合法，right左移到4。
- 此时left=4，right=4，相遇，循环结束。
- 返回left=4。
再看一个需要交换的例子：[5, 1, 2, 3, 4]，k=3。
- left=0指向5，大于等于3，停住。
- right=4指向4，大于等于3，right左移到3。
- right=3指向3，大于等于3，right左移到2。
- right=2指向2，小于3，停住。
- left=0 < right=2，交换arr[0]和arr[2]，数组变成
[2, 1, 5, 3, 4]。 - left右移到1，指向1，小于3，left右移到2。
- left=2指向5，大于等于3，停住。
- right左移到1，此时left=2 > right=1，循环结束。
- 返回left=2。验证：左边
[2,1]都小于3，右边[5,3,4]都大于等于3，正确。
3.2 代码实现与逐行注释
def partition_array(nums, k): """ 将数组划分为左边小于k、右边大于等于k两部分 返回第一个大于等于k的元素索引 """ if not nums: return 0 left, right = 0, len(nums) - 1 while left <= right: # 左指针找第一个大于等于k的元素 while left <= right and nums[left] < k: left += 1 # 右指针找第一个小于k的元素 while left <= right and nums[right] >= k: right -= 1 # 如果两个指针没有相遇，交换这对错位元素 if left < right: nums[left], nums[right] = nums[right], nums[left] left += 1 right -= 1 return left这段代码有几个细节值得展开说。第一，外层循环条件是left <= right而不是left < right，因为当left和right相等时，那个位置的元素还需要判断一次。第二，内层两个while循环都带了left <= right的保护条件，防止指针越界。第三，交换后left和right都移动了一步，因为交换后的两个位置都已经满足条件了，不需要再检查。
3.3 另一种写法：快慢指针
除了左右双指针，还有一种快慢指针的写法。慢指针指向“下一个小于k的元素应该放的位置”，快指针遍历整个数组，遇到小于k的元素就交换到慢指针位置，慢指针右移。这种写法在某些场景下更直观，尤其是当你需要保持左边部分的相对顺序时（虽然本题不要求）。
def partition_array_slow_fast(nums, k): if not nums: return 0 slow = 0 for fast in range(len(nums)): if nums[fast] < k: nums[slow], nums[fast] = nums[fast], nums[slow] slow += 1 return slow这种写法的时间复杂度同样是O(n)，空间O(1)，但交换次数可能比左右双指针多。左右双指针每次交换能解决两个错位元素，快慢指针每次只能解决一个。不过快慢指针的代码更简洁，不容易出边界错误，新手可以先从这个版本入手。
实操心得：如果面试官没有特别要求“交换次数最少”，快慢指针版本其实更稳妥，因为它的边界条件更简单，不容易写出死循环。我在实际面试中如果时间紧张，会优先写快慢指针版本，确认正确后再根据面试官要求优化。
4. 边界情况全梳理与测试用例设计
4.1 必须覆盖的六种边界情况
这道题的边界情况比想象中多，我整理了一个表格，把每种情况的表现和预期结果都列出来：
| 场景 | 输入示例 | k值 | 预期返回 | 说明 |
|---|---|---|---|---|
| 空数组 | [] | 5 | 0 | 直接返回0 |
| 单元素小于k | [3] | 5 | 1 | 唯一元素在左边 |
| 单元素大于等于k | [7] | 5 | 0 | 唯一元素在右边 |
| 全部小于k | [1,2,3] | 10 | 3 | 返回数组长度 |
| 全部大于等于k | [5,6,7] | 3 | 0 | 返回0 |
| 全部等于k | [4,4,4] | 4 | 0 | 所有元素都在右边 |
这六种情况覆盖了指针可能出现的所有极端位置。特别是“全部等于k”这种情况，很多人会误以为应该返回中间某个位置，但实际上所有元素都大于等于k，所以第一个大于等于k的位置就是索引0。
4.2 随机测试与对数器验证
写完代码后，怎么确认它真的正确？我习惯写一个暴力解法作为对数器，然后随机生成大量测试用例对比结果。暴力解法很简单：开两个新数组，遍历原数组，小于k的放左边数组，大于等于k的放右边数组，最后拼起来，返回左边数组的长度。
import random def brute_force(nums, k): left_part = [x for x in nums if x < k] right_part = [x for x in nums if x >= k] return len(left_part) def random_test(): for _ in range(10000): n = random.randint(0, 20) nums = [random.randint(-10, 10) for _ in range(n)] k = random.randint(-10, 10) nums1 = nums.copy() nums2 = nums.copy() result1 = partition_array(nums1, k) result2 = brute_force(nums2, k) if result1 != result2: print(f"不一致！nums={nums}, k={k}, 双指针={result1}, 暴力={result2}") return False # 验证划分性质 for i in range(result1): if nums1[i] >= k: print(f"左边出现大于等于k的元素！nums={nums}, k={k}") return False for i in range(result1, len(nums1)): if nums1[i] < k: print(f"右边出现小于k的元素！nums={nums}, k={k}") return False print("全部通过") return True random_test()这个对数器做了两层验证：第一层对比返回值是否与暴力解法一致，第二层验证划分后的数组是否真的满足“左边全小于k，右边全大于等于k”。两层验证都通过，才能说明代码是正确的。
4.3 性能测试与优化空间
虽然这道题的理论最优解就是O(n)时间O(1)空间，但不同写法在实际运行时的常数因子差异还是值得关注的。我做过一组简单的性能对比，在100万个随机整数上运行：
| 写法 | 耗时（毫秒） | 交换次数 |
|---|---|---|
| 左右双指针 | 约45 | 约25万 |
| 快慢指针 | 约52 | 约50万 |
| 排序后二分 | 约180 | 不适用 |
左右双指针在交换次数上有明显优势，因为每次交换解决两个错位元素。快慢指针虽然交换次数多，但代码更简单，实际差异在大多数场景下可以忽略。排序解法虽然也能得到正确答案（排序后第一个大于等于k的位置就是分界点），但时间复杂度高了一个量级，不推荐。
注意：上面的性能数据是基于特定硬件和编程语言的粗略测试，不同环境下数值会有差异，但相对关系基本一致。重点不是具体数字，而是理解不同写法在常数因子上的差异来源。
5. 从这道题延伸出去：原地划分的通用模板
5.1 快速排序中的partition
这道题的解法其实就是快速排序中partition步骤的简化版。快速排序的partition需要选一个pivot，然后把小于pivot的放左边，大于pivot的放右边，最后返回pivot的最终位置。区别在于快速排序还需要把pivot本身放到正确位置，而这道题不需要。
如果你理解了这道题的双指针写法，快速排序的partition代码基本就是在这基础上加几行：
def partition_for_quicksort(nums, left, right): pivot = nums[right] # 选最右元素作为基准 i = left for j in range(left, right): if nums[j] < pivot: nums[i], nums[j] = nums[j], nums[i] i += 1 nums[i], nums[right] = nums[right], nums[i] return i这段代码用的是快慢指针思路，最后把pivot换到分界点。你看，核心逻辑跟上面的partition_array_slow_fast几乎一模一样，只是多了最后一步pivot归位。
5.2 荷兰国旗问题的三路划分
如果题目变成“把数组分成小于k、等于k、大于k三部分”，那就是经典的荷兰国旗问题。解法是用三个指针：low指向小于区域的右边界，mid遍历数组，high指向大于区域的左边界。这个问题的难度比两路划分高一个档次，但底层思路仍然是双指针的扩展。
def three_way_partition(nums, k): low, mid, high = 0, 0, len(nums) - 1 while mid <= high: if nums[mid] < k: nums[low], nums[mid] = nums[mid], nums[low] low += 1 mid += 1 elif nums[mid] == k: mid += 1 else: nums[mid], nums[high] = nums[high], nums[mid] high -= 1 return low, high三路划分在工程中很有用，比如数据清洗时把数据按“合格、待定、不合格”分类，或者按优先级把任务分成三档。你把这题的两路划分吃透了，三路划分也就是多一个指针的事。
5.3 实际工程中的应用场景
原地划分在工程中出现的频率比想象中高。举几个我实际遇到过的场景：
第一个是日志分类。服务器日志按级别划分，ERROR级别的日志需要单独处理，其他级别的正常归档。用原地划分可以在一次遍历中把ERROR日志移到数组前部，然后只对前部进行处理，避免全量扫描。
第二个是数据预处理。机器学习训练数据中，有些样本需要特殊处理（比如缺失值过多的样本），可以用原地划分把这些样本移到一边，后续只对正常样本做特征工程。
第三个是内存优化。在嵌入式设备或内存受限的环境中，开新数组可能直接导致内存不足，原地划分是唯一可行的方案。这也是为什么面试官特别看重O(1)空间解法——它代表了你对资源约束的敏感度。
实操心得：在实际工程中，如果数据量不大且内存充足，开新数组的写法其实更安全，因为不容易出bug。原地划分的价值主要体现在性能敏感和内存受限的场景。选择哪种写法，要根据具体场景权衡，不要为了“炫技”而强行原地操作。
6. 常见问题排查与调试技巧实录
6.1 死循环问题
双指针写法最容易出的问题是死循环。典型症状是程序跑着跑着卡住了，或者在某些输入下永远不返回。原因通常是内层while循环没有正确移动指针，或者外层循环条件写错。
排查方法很简单：在循环里打印left和right的值，观察它们是否在正常移动。如果发现某次迭代后left和right都没变，那就是死循环了。常见的原因包括：内层while条件写成了nums[left] <= k（应该是< k），或者交换后忘记移动指针。
# 错误示范：交换后没有移动指针 if left < right: nums[left], nums[right] = nums[right], nums[left] # 忘记 left += 1 和 right -= 1，导致死循环6.2 返回值差一问题
返回值差一是另一个高频错误。有人返回left - 1，有人返回right，结果在某些边界情况下跟预期差1。记住一个原则：循环结束时，left指向的就是第一个大于等于k的位置。因为left在移动过程中，要么因为nums[left] >= k停住，要么因为left > right停住。无论哪种情况，left左边的所有元素都已经确认小于k。
如果你不确定，用“全部小于k”这个用例验证一下：数组[1,2,3]，k=10。left会一直右移到3，right从2开始一直左移，最终left=3，right=-1，循环结束，返回3。正确。
6.3 交换后数组状态不符合预期
有时候代码不报错，返回值也对，但划分后的数组不满足“左边全小于k，右边全大于等于k”。这种情况通常是交换逻辑有问题，比如交换后没有正确更新指针，导致某些元素被跳过或重复处理。
排查方法是写一个验证函数，在每次划分后检查数组是否满足性质：
def validate(nums, k, idx): for i in range(idx): if nums[i] >= k: return False for i in range(idx, len(nums)): if nums[i] < k: return False return True把这个验证函数加到随机测试里，一旦发现不满足的情况就打印出错的输入，然后手动模拟一遍，很快就能定位问题。
6.4 常见问题速查表
| 问题现象 | 可能原因 | 排查方法 | 解决方案 |
|---|---|---|---|
| 死循环 | 指针未移动或循环条件错误 | 打印left/right值 | 检查内层while条件和交换后的指针移动 |
| 返回值差1 | 返回了left-1或right | 用全小于k的用例验证 | 统一返回left |
| 数组状态错误 | 交换逻辑有误 | 加验证函数 | 检查交换后指针是否正确更新 |
| 空数组崩溃 | 未处理空数组 | 加空数组测试用例 | 开头加if not nums: return 0 |
| 全部等于k时返回错误 | 边界条件未覆盖 | 加全部等于k的测试用例 | 确认返回0而非其他值 |
提示：调试这类指针问题时，最有效的方法不是盯着代码看，而是拿一张纸画出数组和指针的位置，一步一步手动模拟。我见过太多人对着屏幕发呆半小时，不如动手画五分钟。
7. 不同语言的实现差异与注意事项
7.1 Python的交换与切片
Python的交换写法a, b = b, a非常简洁，不需要临时变量。但要注意，Python的列表是可变对象，函数内修改会影响外部。如果你不希望修改原数组，需要先nums = nums.copy()。
另外，Python的切片操作虽然方便，但在原地划分场景下要慎用。比如nums[:idx]会创建一个新列表，如果在大循环里反复切片，性能会急剧下降。
7.2 Java的数组与引用
Java中数组是引用类型，传参时传的是引用的拷贝，但指向的是同一个数组对象，所以函数内修改数组元素会影响外部。Java没有Python那样的多变量交换语法，需要显式用临时变量：
int temp = nums[left]; nums[left] = nums[right]; nums[right] = temp;Java的数组长度是nums.length（属性），不是方法，不要写成nums.length()。
7.3 C++的指针与引用
C++中可以用指针或引用来操作数组。用vector<int>& nums传引用可以避免拷贝，用swap(nums[left], nums[right])交换元素。C++的vector有size()方法，注意不要跟数组的sizeof混淆。
C++的一个优势是可以直接用指针运算，但在现代C++中更推荐用索引或迭代器，可读性更好，也不容易出错。
7.4 JavaScript的数组操作
JavaScript的数组是动态的，交换可以用解构赋值[nums[left], nums[right]] = [nums[right], nums[left]]。注意JavaScript的数组索引越界不会报错，只会返回undefined，所以边界检查要格外小心。
function partitionArray(nums, k) { if (nums.length === 0) return 0; let left = 0, right = nums.length - 1; while (left <= right) { while (left <= right && nums[left] < k) left++; while (left <= right && nums[right] >= k) right--; if (left < right) { [nums[left], nums[right]] = [nums[right], nums[left]]; left++; right--; } } return left; }不管用哪种语言，核心逻辑完全一致。语言差异只影响语法细节，不影响算法思路。如果你在面试中遇到这道题，用你最熟悉的语言写就行，面试官看重的是思路清晰和边界处理完整，而不是语言特性。
8. 刷题之外的思考：这道题教会我的事
这道题我前前后后在不同场合写过不下二十遍，每次都有新的体会。最开始我觉得它太简单，不值得花时间；后来带新人时发现，正是这种“简单”题目最能看出一个人的基本功。一个人如果能把这道题的边界情况全部考虑到、代码一遍过、还能说清楚为什么这样写，那他的编码习惯一定不会差。
另一个体会是，很多算法题的价值不在于题目本身，而在于它背后的模式。这道题背后的“双指针原地划分”模式，在快速排序、荷兰国旗问题、数据分类、内存优化等场景中反复出现。你掌握了一个模式，就能解决一类问题，这比刷一百道互不相关的题目效率高得多。
最后说一个实际工作中的小技巧。我在处理数据清洗任务时，经常需要把满足某些条件的数据移到一边。以前我会用filter或者列表推导式开新数组，后来发现数据量大时内存吃不消。改用原地划分后，内存占用直接降了一个数量级。这个技巧我用了好几年，每次都能帮上忙。
