这道题要求原地轮转数组空间 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], k3实际等价于k1因为3 % 2 1。所以第一步永远是k % n。第一反应开一个新数组最直接的想法——计算每个元素的新位置放到新数组里。classSolutionExtra:defrotate(self,nums:List[int],k:int)-None:nlen(nums)k%n rotatednums[-k:]nums[:-k]ifk!0elsenums[:]nums[:]rotated维度值说明时间O(n)切片拼接空间O(n)额外数组Python 的切片写起来确实爽但空间 O(n) 不满足进阶要求。思路没问题但我们需要想个原地的方法。第二反应一个一个挪能不能像冒泡排序一样每次把最后一个元素挪到前面重复k次for_inrange(k):lastnums[-1]foriinrange(n-1,0,-1):nums[i]nums[i-1]nums[0]last维度值说明时间O(n × k)k 很大时直接超时空间O(1)原地空间满足了但时间炸了。k最大可以到 10^5n也可以到 10^5O(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:nlen(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):whileleftright:nums[left],nums[right]nums[right],nums[left]left1right-1维度值说明时间O(n)每个元素被交换约 2 次空间O(1)原地交换只用了两个指针跑一遍示例 1nums [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] ✓跑一遍示例 2nums [-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。如果不取模k3, n2时会出错。这行代码看似不起眼但不写就完蛋。类似的边界处理还有k0时跳过翻转不过代码本身能正确处理这种情况。完整测试代码fromtypingimportListclassSolution:defrotate(self,nums:List[int],k:int)-None:nlen(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:whileleftright:nums[left],nums[right]nums[right],nums[left]left1right-1if__name____main__:sSolution()nums[1,2,3,4,5,6,7]s.rotate(nums,3)print(fk3:{nums})nums[-1,-100,3,99]s.rotate(nums,2)print(fk2:{nums})nums[1]s.rotate(nums,0)print(fk0:{nums})nums[1,2]s.rotate(nums,3)print(fk3, n2 → k%21:{nums})相关题目推荐LeetCode 88 · 合并两个有序数组同样是反过来操作的思路LeetCode 151 · 反转字符串中的单词三次翻转的经典应用LeetCode 541 · 反转字符串 II翻转操作的变体
