LeetCode 977简单对撞双指针
有序数组的平方 图解题解
这道题到底在问什么
nums 按非递减顺序排序（可能有负数）。返回「每个数平方后再按非递减排序」的数组。
- 输入
- nums = [-4,-1,0,3,10]
- 输出
- [0,1,9,16,100]
最优解：一步一步想明白
- 3记住这条「平方最大值必在两端 → 双指针比两端、大的从结果末尾往前放」，下面每帧都在套它。
- 4比较两端：左端 nums[0]=-7 平方得 49，右端 nums[10]=11 平方得 121。右边平方更大，它该放进当前结果末尾的空位。
- 5把较大的 121（来自 nums[10]=11）填入结果末尾的空位（绿色标记已消费的下标 10）。下一帧这个指针就向内移一格，继续比较剩下的区间。
- 6比较两端：左端 nums[0]=-7 平方得 49，右端 nums[9]=9 平方得 81。右边平方更大，它该放进当前结果末尾的空位。
- 7把较大的 81（来自 nums[9]=9）填入结果末尾的空位（绿色标记已消费的下标 9）。下一帧这个指针就向内移一格，继续比较剩下的区间。
- 8比较两端：左端 nums[0]=-7 平方得 49，右端 nums[8]=8 平方得 64。右边平方更大，它该放进当前结果末尾的空位。
- 9把较大的 64（来自 nums[8]=8）填入结果末尾的空位（绿色标记已消费的下标 8）。下一帧这个指针就向内移一格，继续比较剩下的区间。
- 10比较两端：左端 nums[0]=-7 平方得 49，右端 nums[7]=6 平方得 36。左边平方更大（或相等），它该放进当前结果末尾的空位。
- 11把较大的 49（来自 nums[0]=-7）填入结果末尾的空位（绿色标记已消费的下标 0）。下一帧这个指针就向内移一格，继续比较剩下的区间。
- 12比较两端：左端 nums[1]=-5 平方得 25，右端 nums[7]=6 平方得 36。右边平方更大，它该放进当前结果末尾的空位。
- 13把较大的 36（来自 nums[7]=6）填入结果末尾的空位（绿色标记已消费的下标 7）。下一帧这个指针就向内移一格，继续比较剩下的区间。
- 14比较两端：左端 nums[1]=-5 平方得 25，右端 nums[6]=4 平方得 16。左边平方更大（或相等），它该放进当前结果末尾的空位。
- 15把较大的 25（来自 nums[1]=-5）填入结果末尾的空位（绿色标记已消费的下标 1）。下一帧这个指针就向内移一格，继续比较剩下的区间。
- 16比较两端：左端 nums[2]=-3 平方得 9，右端 nums[6]=4 平方得 16。右边平方更大，它该放进当前结果末尾的空位。
- 17把较大的 16（来自 nums[6]=4）填入结果末尾的空位（绿色标记已消费的下标 6）。下一帧这个指针就向内移一格，继续比较剩下的区间。
- 18比较两端：左端 nums[2]=-3 平方得 9，右端 nums[5]=2 平方得 4。左边平方更大（或相等），它该放进当前结果末尾的空位。
- 19把较大的 9（来自 nums[2]=-3）填入结果末尾的空位（绿色标记已消费的下标 2）。下一帧这个指针就向内移一格，继续比较剩下的区间。
- 20比较两端：左端 nums[3]=-1 平方得 1，右端 nums[5]=2 平方得 4。右边平方更大，它该放进当前结果末尾的空位。
- 21把较大的 4（来自 nums[5]=2）填入结果末尾的空位（绿色标记已消费的下标 5）。下一帧这个指针就向内移一格，继续比较剩下的区间。
- 22比较两端：左端 nums[3]=-1 平方得 1，右端 nums[4]=0 平方得 0。左边平方更大（或相等），它该放进当前结果末尾的空位。
- 23把较大的 1（来自 nums[3]=-1）填入结果末尾的空位（绿色标记已消费的下标 3）。下一帧这个指针就向内移一格，继续比较剩下的区间。
- 24比较两端：左端 nums[4]=0 平方得 0，右端 nums[4]=0 平方得 0。左边平方更大（或相等），它该放进当前结果末尾的空位。
- 25把较大的 0（来自 nums[4]=0）填入结果末尾的空位（绿色标记已消费的下标 4）。下一帧这个指针就向内移一格，继续比较剩下的区间。
- 26一趟扫完，结果数组从后往前被填满，正好是升序：[0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 121]。左右指针各只走一遍，O(n)，比「先平方再排序」的 O(n log n) 更快。
⚠️ 容易写错的地方
✗ 错：从结果数组开头往后填
✓ 对：要从末尾 w=n-1 往前填
每次比较得到的是当前剩余里的最大值，最大值该放最后
✗ 错：只看右端（以为正数平方最大）
✓ 对：必须比较两端平方
最左的大负数平方后可能比最右的正数还大
✗ 错：先平方再 sort
✓ 对：能过但慢
丢掉了「原数组已升序」这个条件，退化成 O(n log n)
完整代码（Python / C++ / Java）
Python
def sortedSquares(nums):
n = len(nums)
res = [0] * n
l, r, w = 0, n - 1, n - 1 # w 从末尾往前填
while l <= r:
ls, rs = nums[l] ** 2, nums[r] ** 2
if ls >= rs: # 左端平方更大
res[w] = ls; l += 1
else: # 右端平方更大
res[w] = rs; r -= 1
w -= 1
return resC++
vector<int> sortedSquares(vector<int>& nums){
int n = nums.size();
vector<int> res(n);
int l = 0, r = n - 1, w = n - 1;
while(l <= r){
int ls = nums[l]*nums[l], rs = nums[r]*nums[r];
if(ls >= rs){ res[w] = ls; l++; }
else { res[w] = rs; r--; }
w--;
}
return res;
}Java
public int[] sortedSquares(int[] nums) {
int n = nums.length;
int[] res = new int[n];
int l = 0, r = n - 1, w = n - 1; // w 从末尾往前填
while (l <= r) {
int ls = nums[l] * nums[l];
int rs = nums[r] * nums[r];
if (ls >= rs) { res[w] = ls; l++; } // 左端平方更大
else { res[w] = rs; r--; } // 右端平方更大
w--;
}
return res;
}复杂度
时间
O(n)
l、r 各走一遍，合计线性
空间
O(n)
结果数组；不计返回值则 O(1)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 有序数组的平方 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
如果不许用双指针，最简单的写法是什么？复杂度？+
把每个数平方后直接 sort，O(n log n)。能过但没利用「原数组已升序」，比双指针 O(n) 慢。
为什么结果要从后往前填，而不是从前往后？+
双指针每次比较得到的是「当前剩余区间里平方最大的数」，最大的应放结果末尾，所以 w 从 n-1 递减。若想从前往后填，就得改成比较两端取较小者，逻辑等价但不如取较大值直观。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 有序数组的平方 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
把这道题真正拿下
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。