2025-06-19：识别数组中的最大异常值。用go语言，你有一个长度为 n 的整数数组 nums，其中恰好有 n-2 个元素属于“特殊数字”类别。剩下的两个元素中，一个等于所有这些特殊数字的总和，另一个是一个“异常值”。

这里，“异常值”的意思是：它既不是数组中那些特殊数字，也不是所有特殊数字的和。

题目要求特殊数字、和、异常值对应的索引互不相同（位置不同），但它们的数值可以相同。

需要你找出数组中可能的最大“异常值”。

3 <= nums.length <= 100000。

-1000 <= nums[i] <= 1000。

输入保证 nums 中至少存在 一个 可能的异常值。

输入： nums = [2,3,5,10]。

输出： 10。

解释：

特殊数字可以是 2 和 3，因此和为 5，异常值为 10。

题目来自力扣3371。

解决思路

我们需要找到一个“异常值” y，满足以下条件：

1. 1. 存在 n-2 个“特殊数字”，它们的和为 s。
2. 2. 数组中有一个元素等于 s（“和”）。
3. 3. 另一个元素 y 是“异常值”，即 y 不等于 s，且 y 不是任何“特殊数字”。
4. 4. 我们需要找到所有可能的 y 中的最大值。

具体步骤

1. 1. 遍历所有可能的“和”候选：
2. o 对于数组中的每一个元素 y，假设 y 是“异常值”，那么剩下的 n-1 个元素中：
3. o 有 n-2 个“特殊数字”。
4. o 有 1 个“和”（即这些特殊数字的和）。
5. o 我们需要检查是否存在这样的“和” s 满足：
6. o s 是剩下的 n-1 个元素中的某一个。
7. o s 等于其他 n-2 个“特殊数字”的和。
8. o 具体来说：
9. o 对于当前假设的“异常值” y，计算剩余 n-1 个元素的总和 total - y。
10. o 因为“特殊数字”有 n-2 个，它们的和是 s，所以 total - y = s + s（因为“和” s 也是剩下的 n-1 个元素之一）。
11. o 因此，s = (total - y) / 2。
12. o 我们需要检查：
13. o (total - y) 是否能被 2 整除（即 s 是整数）。
14. o s 是否存在于剩下的 n-1 个元素中（即 s 是“和”）。
15. o y 不能是“特殊数字”或“和”（即 y != s 且 y 不是“特殊数字”）。
16. o 但题目允许数值相同，只要索引不同即可，所以 y 可以和 s 或“特殊数字”数值相同，只要位置不同。
17. 2. 验证“和” s 的存在性：
18. o 对于每个 y，计算 s = (total - y) / 2。
19. o 检查 s 是否在数组中：
20. o 如果 s 在数组中，且 (total - y) 是偶数，则 y 可能是“异常值”。
21. o 需要确保 s 和 y 的索引不同（题目已保证）。
22. 3. 统计频率以优化检查：
23. o 使用哈希表（如 map）统计每个数字的频率。
24. o 对于每个 y：
25. o 计算 t = (total - y)。
26. o 如果 t 是偶数，则 s = t / 2。
27. o 检查 s 是否在哈希表中：
28. o 如果 s 就是 y，则需要 s 出现至少 2 次（因为 y 和 s 需要是不同的索引）。
29. o 如果 s 不是 y，则需要 s 出现至少 1 次。
30. o 如果满足条件，则 y 是一个可能的“异常值”。
31. 4. 收集所有可能的“异常值”并取最大值：
32. o 遍历数组，按照上述方法收集所有可能的 y。
33. o 返回其中最大的 y。

时间复杂度和空间复杂度

• o 时间复杂度：
• o 遍历数组计算 total：O(n)。
• o 构建哈希表 cnt：O(n)。
• o 遍历数组检查每个 y：O(n)。
• o 每次检查 s 是否在哈希表中：O(1)。
• o 总时间复杂度：O(n)。
• o 空间复杂度：
• o 哈希表 cnt 存储 n 个元素的频率：O(n)。
• o 其他变量（如 total、ans 等）：O(1)。
• o 总空间复杂度：O(n)。

总结

• o 算法通过遍历数组两次（一次计算总和，一次检查“异常值”）和哈希表查询，高效地找到最大“异常值”。
• o 时间复杂度和空间复杂度均为 O(n)，适用于题目给定的约束条件。

Go完整代码如下：

.

package main

import (
    "fmt"
    "math"
)

func getLargestOutlier(nums []int)int {
    cnt := map[int]int{}
    total := 0
    for _, x := range nums {
        cnt[x]++
        total += x
    }

    ans := math.MinInt
    for _, y := range nums {
        t := total - y*2
        if cnt[t] > 1 || cnt[t] > 0 && t != y {
            ans = max(ans, t)
        }
    }
    return ans
}

func main() {
    nums := []int{2, 3, 5, 10}
    fmt.Println(getLargestOutlier(nums))
}

Python完整代码如下：

.

# -*-coding:utf-8-*-

def get_largest_outlier(nums):
    from collections import Counter
    cnt = Counter(nums)
    total = sum(nums)
    ans = float('-inf')

    for y in nums:
        t = total - 2 * y
        if cnt[t] > 1 or (cnt[t] > 0 and t != y):
            ans = max(ans, t)
    return ans

if __name__ == "__main__":
    nums = [2, 3, 5, 10]
    print(get_largest_outlier(nums))

·

我们相信Go语言和算法为普通开发者提供了困境的“面试利器”，并致力于分享全面的编程知识。在这里，您可以找到最新的Go语言教程、算法解析、提升面试竞争力的秘籍以及行业动态。

欢迎关注“福大规模架构师每日一题”，让 Go 语言和算法助力您的职业发展

·