LeetCode 题解工作台
识别数组中的最大异常值
给你一个整数数组 nums 。该数组包含 n 个元素，其中 恰好 有 n - 2 个元素是 特殊数字 。剩下的 两个 元素中，一个是所有 特殊数字 的 和 ，另一个是 异常值 。 异常值 的定义是：既不是原始特殊数字之一，也不是表示元素和的那个数。 注意 ，特殊数字、和 以及 异常值 的下标必须 不…
4
题型
7
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
我们用一个哈希表 记录数组 中每个元素出现的次数。 接下来，我们枚举数组 中的每个元素 作为可能的异常值，对于每个 ，我们计算数组 中除了 之外的所有元素的和 ，如果 不是偶数，或者 的一半不在 中，那么 不满足条件，我们跳过这个 。否则，如果 不等于 的一半，或者 在 中出现的次数大于 ，那么 是一个可能的异常值，我们更新答案。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个整数数组 nums。该数组包含 n 个元素，其中 恰好 有 n - 2 个元素是 特殊数字 。剩下的 两个 元素中，一个是所有 特殊数字 的 和 ，另一个是 异常值 。
异常值 的定义是：既不是原始特殊数字之一，也不是表示元素和的那个数。
注意，特殊数字、和 以及 异常值 的下标必须 不同 ，但可以共享 相同 的值。
返回 nums 中可能的 最大异常值。
示例 1：
输入： nums = [2,3,5,10]
输出： 10
解释：
特殊数字可以是 2 和 3，因此和为 5，异常值为 10。
示例 2：
输入： nums = [-2,-1,-3,-6,4]
输出： 4
解释：
特殊数字可以是 -2、-1 和 -3，因此和为 -6，异常值为 4。
示例 3：
输入： nums = [1,1,1,1,1,5,5]
输出： 5
解释：
特殊数字可以是 1、1、1、1 和 1，因此和为 5，另一个 5 为异常值。
提示：
3 <= nums.length <= 105-1000 <= nums[i] <= 1000- 输入保证
nums中至少存在 一个 可能的异常值。
解题思路
方法一：哈希表 + 枚举
我们用一个哈希表 记录数组 中每个元素出现的次数。
接下来，我们枚举数组 中的每个元素 作为可能的异常值，对于每个 ，我们计算数组 中除了 之外的所有元素的和 ，如果 不是偶数，或者 的一半不在 中，那么 不满足条件，我们跳过这个 。否则，如果 不等于 的一半，或者 在 中出现的次数大于 ，那么 是一个可能的异常值，我们更新答案。
枚举结束后，返回答案即可。
时间复杂度 ，空间复杂度 。其中 为数组 的长度。
class Solution:
def getLargestOutlier(self, nums: List[int]) -> int:
s = sum(nums)
cnt = Counter(nums)
ans = -inf
for x, v in cnt.items():
t = s - x
if t % 2 or cnt[t // 2] == 0:
continue
if x != t // 2 or v > 1:
ans = max(ans, x)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on iterating the array and verifying sums, typically O(n^2) without optimization but can be reduced to O(n) with hash-based lookups. Space complexity is O(n) for storing counts in a hash table. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
They may emphasize the array sum pattern to check your understanding of outlier detection.
- question_mark
Expect questions on optimizing the brute force check using hash maps or counting arrays.
- question_mark
They might hint at arrays with repeated values to test your handling of edge cases.
常见陷阱
外企场景- error
Assuming all numbers are distinct and ignoring repeated values that affect the sum.
- error
Failing to correctly identify the sum element versus the outlier during verification.
- error
Using inefficient nested loops without leveraging a hash table, causing timeouts for large arrays.
进阶变体
外企场景- arrow_right_alt
Return the smallest outlier instead of the largest in arrays with repeated candidates.
- arrow_right_alt
Handle arrays where more than one outlier exists and return all valid outliers.
- arrow_right_alt
Given negative numbers, find the largest outlier while ensuring sum calculations handle negatives correctly.