题意
给定一个数组，数组包含n个元素，其中n-2个元素称为special number，其余两个元素一个是这些special number的元素和， 另一个称为outlier，我要找到最大的outlier
链接
https://leetcode.com/problems/identify-the-largest-outlier-in-an-array/description/
思考
这题的数字范围是10^5,我需要一个O(n)的解法，判断某个元素是这些special number的元素和是比较容易的，可以用hashmap来做
思路
建立hashmap统计每个数字出现的次数，以及所有元素之和total。枚举所有的元素，假定第i位元素是outlier，那么剩下来的元素，其中有一个元素一定是所有special元素的和，也就是 ( t o t a l − n u m s [ i ] ) / 2 (total-nums[i]) / 2 (total−nums[i])/2，可以用之前的hashmap来判断 ( t o t a l − n u m s [ i ] ) / 2 (total-nums[i]) / 2 (total−nums[i])/2是否出现过，如果出现过，那么第i位元素就是outlier，如果没出现过那么第i位元素不是outlier。
代码
class Solution {
public:int getLargestOutlier(vector<int>& nums) {unordered_map<int, int> mp;int n = nums.size();int t = 0;int res = INT_MIN;for(int i = 0; i < n; i++) {mp[nums[i]]++;t += nums[i];}for(int i = 0; i < n; i++) {int cur = t - nums[i];mp[nums[i]]--;if(cur % 2 == 0 && mp.count(cur / 2) && mp[cur / 2] > 0) {res = max(res, nums[i]);}mp[nums[i]]++;}return res;}
};
时间复杂度： O ( n ) O(n) O(n)
空间复杂度： O ( n ) O(n) O(n)
