LeetCode 补充题 160. 有序数组的不同平方值计数
题目描述
:::fold-green 相关原题
LeetCode 原题： ✅ 977. 有序数组的平方
:::
给定非降序的 32 位整数数组
nums，返回所有元素平方后不同数值的个数。要求时间复杂度为
O(n)，额外空间为O(1)，且不修改数组。
示例 1：
输入：
nums = [-3,-1,-1,0,1,3,4]
输出：4
解释： 平方后的不同值是 0、1、9、16；正负同绝对值及重复元素只计一次。
提示：
- 输入为非降序的
32位整数数组。 - 要求
O(n)时间、O(1)额外空间。 - 不能修改输入。
题意分析
两个整数平方相等，当且仅当它们的绝对值相等。只计不同平方值的数量，因此无需真的相乘或创建平方数组；利用原数组有序性，从两端处理绝对值即可。
解法：按两端绝对值整段去重
核心思路
[!blue]
剩余区间的最大绝对值必在两端：负数越靠左绝对值越大，非负数越靠右越大。取两端绝对值较大者
value，计入一种新的平方结果。随后同时从左右两端跳过所有绝对值等于
value的元素。重复值以及一正一负的对应值都在这一轮消耗完，因此下轮不会再次计数。每次至少消耗一个元素，直到区间为空。取绝对值前先提升到 64 位，保证 32 位最小负数也能正确处理。空数组不进入循环，返回 0；两侧跳过时都检查指针是否交错，避免同一位置处理后越界。
解题步骤
- 比较两端元素的绝对值，确定当前最大的平方等价类并计数一次。
- 从左右两端同时跳过所有该绝对值的元素。
- 重复直到两指针交错，返回不同平方值数量。
代码实现
class Solution {
public int distinctSquares(int[] a) {
int left = 0;
int right = a.length - 1;
int count = 0;
while (left <= right) {
long value = Math.max(Math.abs((long) a[left]), Math.abs((long) a[right]));
count++;
while (left <= right && Math.abs((long) a[left]) == value) {
left++;
}
while (left <= right && Math.abs((long) a[right]) == value) {
right--;
}
}
return count;
}
}
func distinctSquares(a []int) int {
abs := func(x int) int64 {
v := int64(x)
if v < 0 {
return -v
}
return v
}
left, right, count := 0, len(a)-1, 0
for left <= right {
value := max(abs(a[left]), abs(a[right]))
count++
for left <= right && abs(a[left]) == value {
left++
}
for left <= right && abs(a[right]) == value {
right--
}
}
return count
}
复杂度分析
- 时间复杂度：$O(n)$。
- 空间复杂度：额外空间 $O(1)$。
关键点总结
[!green]
平方是否相同只取决于绝对值，不需要做乘法；相同绝对值的正负两侧必须在同一轮去重。
易错点总结
[!yellow]
先转64位再取绝对值，避免32位最小负数溢出；两侧都要去重。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 977. 有序数组的平方 | 简单 | 同样从两端选择最大绝对值，本题只数不同结果，不实际计算或保存平方数组。 |
| 26. 删除有序数组中的重复项 | 简单 | 复用有序数据相邻重复项整段跳过的思路，这里还要合并正负相同绝对值。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！