LeetCode 189 · 轮转数组：三次翻转，原地搞定的神仙操作
这道题要求原地轮转数组，空间 O(1)。我第一次看到最优解的时候直接愣住了——三次翻转就能完成？这也太巧妙了。它和 LeetCode 88（合并两个有序数组）的逆向双指针异曲同工：都是通过"反过来操作"来避开冲突。不过这道题的三次翻转更像是数学魔术。
题目长什么样
给定一个整数数组nums，将数组中的元素向右轮转k个位置，其中k是非负数。
输入：nums = [1,2,3,4,5,6,7], k = 3
输出：[5,6,7,1,2,3,4]
说人话就是：每个元素往右挪k步，超出末尾的回到开头。等价于把数组最后k个元素搬到前面来。
注意一个容易忽略的细节：k可以大于数组长度。比如nums=[1,2], k=3，实际等价于k=1（因为3 % 2 = 1）。所以第一步永远是k %= n。
第一反应：开一个新数组
最直接的想法——计算每个元素的新位置，放到新数组里。
classSolutionExtra:defrotate(self,nums:List[int],k:int)->None:n=len(nums)k%=n rotated=nums[-k:]+nums[:-k]ifk!=0elsenums[:]nums[:]=rotated| 维度 | 值 | 说明 |
|---|---|---|
| 时间 | O(n) | 切片拼接 |
| 空间 | O(n) | 额外数组 |
Python 的切片写起来确实爽，但空间 O(n) 不满足进阶要求。思路没问题，但我们需要想个原地的方法。
第二反应：一个一个挪
能不能像冒泡排序一样，每次把最后一个元素挪到前面，重复k次？
for_inrange(k):last=nums[-1]foriinrange(n-1,0,-1):nums[i]=nums[i-1]nums[0]=last| 维度 | 值 | 说明 |
|---|---|---|
| 时间 | O(n × k) | k 很大时直接超时 |
| 空间 | O(1) | 原地 |
空间满足了，但时间炸了。k最大可以到 10^5，n也可以到 10^5，O(n²) 铁定超时。这个方案直接淘汰。
最优解：三次翻转
这是这道题最精妙的地方。先说结论：
轮转 k 步 = 翻转整个数组 + 翻转前 k 个 + 翻转后 n-k 个为什么三次翻转就能搞定？
用示例 1 推一遍就明白了：
原始数组: [1, 2, 3, 4, 5, 6, 7] 期望结果: [5, 6, 7, 1, 2, 3, 4] 观察期望结果的结构： 前 k 个: [5, 6, 7] ← 原来在末尾的那段 后 n-k 个: [1, 2, 3, 4] ← 原来在开头的那段 如果翻转整个数组: [7, 6, 5, 4, 3, 2, 1] ↑ [7,6,5] 是 [5,6,7] 的逆序 [4,3,2,1] 是 [1,2,3,4] 的逆序 再把两段分别翻转回来: 翻转 [7,6,5] → [5,6,7] 翻转 [4,3,2,1] → [1,2,3,4] 最终: [5, 6, 7, 1, 2, 3, 4] ✓本质上就是：翻转两段后再整体翻转 = 交换两段的位置。这是一个数学性质，不需要硬记——理解了"翻转的翻转是还原"就行。
代码如下：
classSolution:defrotate(self,nums:List[int],k:int)->None:n=len(nums)k%=n self.reverse(nums,0,n-1)self.reverse(nums,0,k-1)self.reverse(nums,k,n-1)defreverse(self,nums,left,right):whileleft<right:nums[left],nums[right]=nums[right],nums[left]left+=1right-=1| 维度 | 值 | 说明 |
|---|---|---|
| 时间 | O(n) | 每个元素被交换约 2 次 |
| 空间 | O(1) | 原地交换，只用了两个指针 |
跑一遍示例 1
nums = [1, 2, 3, 4, 5, 6, 7], k = 3, n = 7 第一步: 翻转 [0, 6] [1,2,3,4,5,6,7] → [7,6,5,4,3,2,1] 第二步: 翻转 [0, 2] [7,6,5,...] → [5,6,7,...] 数组: [5,6,7,4,3,2,1] 第三步: 翻转 [3, 6] [...,4,3,2,1] → [...,1,2,3,4] 数组: [5,6,7,1,2,3,4] 最终结果: [5, 6, 7, 1, 2, 3, 4] ✓跑一遍示例 2
nums = [-1, -100, 3, 99], k = 2, n = 4 第一步: 翻转 [0, 3] [-1,-100,3,99] → [99,3,-100,-1] 第二步: 翻转 [0, 1] [99,3,...] → [3,99,...] 数组: [3,99,-100,-1] 第三步: 翻转 [2, 3] [...,-100,-1] → [...,-1,-100] 数组: [3,99,-1,-100] 最终结果: [3, 99, -1, -100] ✓三种解法放在一起看
| 解法 | 时间 | 空间 | 一句话评价 |
|---|---|---|---|
| 额外数组 | O(n) | O(n) | 最直观，Python 切片一行搞定 |
| 逐个挪动 | O(n × k) | O(1) | 会超时，面试别写 |
| 三次翻转 | O(n) | O(1) | 最优解，巧妙且高效 |
这道题教会我什么
翻转是一个强大的基本操作
三次翻转解决轮转——这个技巧不是孤立的。在很多场景下，"翻转"都是极其有用的原子操作：
- 字符串反转：翻转整个字符串
- 回文判断：翻转后和原串比较
- 单词倒序：翻转整个句子，再逐词翻转
- 链表反转：修改指针方向（和数组翻转异曲同工）
掌握了"翻转"这个基本操作，很多看似复杂的问题都能拆解成翻转的组合。
"反过来想"再次登场
和 LeetCode 88 一样，这道题的关键突破也是"反过来"——正向挪动元素会覆盖，那就先翻转。整个系列做下来你会发现，"反过来想"是数组操作中最高频的技巧之一。
k %= n不能忘
k最大可以到 10^5，而n也可能很小（比如 2）。如果不取模，k=3, n=2时会出错。这行代码看似不起眼，但不写就完蛋。类似的边界处理还有k=0时跳过翻转（不过代码本身能正确处理这种情况）。
完整测试代码
fromtypingimportListclassSolution:defrotate(self,nums:List[int],k:int)->None:n=len(nums)k%=n self.reverse(nums,0,n-1)self.reverse(nums,0,k-1)self.reverse(nums,k,n-1)defreverse(self,nums:List[int],left:int,right:int)->None:whileleft<right:nums[left],nums[right]=nums[right],nums[left]left+=1right-=1if__name__=="__main__":s=Solution()nums=[1,2,3,4,5,6,7]s.rotate(nums,3)print(f"k=3:{nums}")nums=[-1,-100,3,99]s.rotate(nums,2)print(f"k=2:{nums}")nums=[1]s.rotate(nums,0)print(f"k=0:{nums}")nums=[1,2]s.rotate(nums,3)print(f"k=3, n=2 → k%=2=1:{nums}")相关题目推荐：
- LeetCode 88 · 合并两个有序数组（同样是"反过来"操作的思路）
- LeetCode 151 · 反转字符串中的单词（三次翻转的经典应用）
- LeetCode 541 · 反转字符串 II（翻转操作的变体）