3371 识别数组中的最大异常值

题目描述#

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

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

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

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

思路#

设数组总和为 total，异常值为 x，特殊数字的和为 sum，则有：

total = sum + x + sum

即：total = 2 * sum + x

推导出：sum = (total - x) / 2

枚举异常值：用哈希表记录每个数字出现的次数，然后枚举每个可能的异常值 x，计算对应的 sum = (total - x) / 2，检查 sum 是否在数组中存在。需要注意 x 和 sum 可能相同的情况（需要至少出现 2 次）。

代码#

class Solution {
    public int getLargestOutlier(int[] nums) {
        int total = 0;
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int num : nums) {
            total += num;
            cnt.merge(num, 1, Integer::sum);
        }

        int ans = Integer.MIN_VALUE;

        for (int x : nums) {
            if ((total - x) % 2 != 0) {
                continue;
            }

            int sum = (total - x) / 2;

            if (!cnt.containsKey(sum)) {
                continue;
            }

            if (x == sum && cnt.get(sum) < 2) {
                continue;
            }

            ans = Math.max(ans, x);
        }

        return ans;
    }
}