题目描述

给你一个整数数组 nums。该数组包含 n 个元素，其中 恰好 有 n - 2 个元素是 特殊数字。剩下的 两个 元素中，一个是这些 特殊数字 的 和，另一个是 异常值。

异常值 的定义是：既不是原始特殊数字之一，也不是表示这些数字元素和的数字。

注意，特殊数字、和 以及 异常值 的下标必须 不同，但可以共享 相同 的值。

返回 nums 中可能的 最大异常值。

样例

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

输出： 10

解释：

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

输入： nums = [-2,-1,-3,-6,4]

输出： 4

解释：

特殊数字可以是 -2、-1 和 -3，因此和为 -6，异常值为 4。

输入： nums = [1,1,1,1,1,5,5]

输出： 5

解释：

特殊数字可以是 1、1、1、1 和 1，因此和为 5，另一个 5 为异常值。

限制

• 3 <= nums.length <= 10^5
• -1000 <= nums[i] <= 1000
• 输入保证 nums 中至少存在 一个 可能的异常值。

算法

(哈希表，枚举) $O(n)$

1. 将所有数字存储哈希表，并求所有数字的总和。
2. 枚举每个数字判定是否可以作为异常值。
3. 如果去除异常值之后的数字之和为偶数，且的数字之和除以 2 后的数字出现在数组中，则可以确定当前数字可以作为异常值。
4. 特别地，如果异常值就是数字之和除以 2，则需要额外判定是否还有另外一个相同数字。

时间复杂度

• 预处理的时间复杂度为 $O(n)$。
• 枚举判定的时间复杂度为 $O(n)$。
• 故总时间复杂度为 $O(n)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储哈希表。

C++ 代码

class Solution {
public:
    int getLargestOutlier(vector<int>& nums) {
        int sum = 0;
        map<int, int> h;

        for (int x : nums) {
            sum += x;
            ++h[x];
        }

        int ans = INT_MIN;
        for (int x : nums) {
            if ((sum - x) % 2 != 0)
                continue;

            int t = (sum - x) / 2;
            if (h.find(t) == h.end())
                continue;

            if (x != t || (x == t && h[t] > 1))
                ans = max(ans, x);
        }

        return ans;
    }
};