1.找出满足差值条件的下标 II
题目
解析
- 核心思想：将绝对值左边拆分为两个不含绝对值的条件：max - nums[j] 和 nums[j] - min；
- 从 index 开始遍历 j ，因为 i <= j - index；
- 两个变量存储 [0，i] 的最大值和最小值下标，作为后续条件判断；
代码
class Solution {
public:vector<int> findIndices(vector<int>& nums, int indexDifference, int valueDifference) {// 时间复杂度：O(n - indexDifference)// 空间复杂度：O(1)int n = nums.size();int min_idx = 0,max_idx = 0;// j - i >= indexDifferencefor(int j = indexDifference;j < n;j ++){int i = j - indexDifference;// 更新 [0,j - indexDifference] 的 min,maxif(nums[i] > nums[max_idx]){max_idx = i;}else if(nums[i] < nums[min_idx]){min_idx = i;}// nums[j] - min >= valueDifferenceif(nums[j] - nums[min_idx] >= valueDifference){return {min_idx,j};}// max - nums[j] >= valueDifferenceif(nums[max_idx] - nums[j] >= valueDifference){return {max_idx,j};}}return {-1,-1};}
};
2.有序三元组中的最大值
题目
解析
- 遍历 k 指针，按照 k -> j -> i 的顺序更新变量值；
- 本题要求最大值，右变量即为 k 指针，左变量最大值由 maxDiff 存储，由于左变量为一个减式，还需要一个变量 preMax 存储被减数最大值；
代码
class Solution {
public:long long maximumTripletValue(vector<int>& nums) {// 时间复杂度：O(n)// 空间复杂度：O(1)long long ans = 0;int maxDiff = 0;// max(nums[i] - nums[j])int preMax = 0;// [0,j - 1]最大值for(int k : nums){// 更新答案，移动 kans = max(ans,1LL * maxDiff * k);// 移动 k 后，原来的 k 可以作为 nums[j]maxDiff = max(maxDiff,preMax - k);// 移动 j 后，原来的 j 可以作为 nums[i]preMax = max(preMax,k);}return ans;}
};
3.识别数组中的最大异常值
题目
解析
- 设异常值为 x，元素和为 y，那么其余 n−2 个数的和也是 y，所以 x+2y = sum；需要计算的即为 x 的最大值。（两数之和）；
- 用哈希表记录每个数的出现次数，每次移除该数，计算完再移入；
- 枚举异常值 x = nums[i]，则 2y = sum − x；如果 sum − x 是偶数，且 y = (sum − x) / 2 存在，那么 x 就是一个异常值。
代码
class Solution {
public:int getLargestOutlier(vector<int>& nums) {// 时间复杂度：O(n)// 空间复杂度：O(n)int n = nums.size();int ans = INT_MIN;int sum = 0;unordered_map<int,int> cnt;// 记录各数字出现次数for(int x : nums){cnt[x] ++;sum += x;}for(int x : nums){cnt[x] --;// 移除计数,坐标不能相等if((sum - x) % 2 == 0 && cnt[(sum - x) / 2] > 0){ans = max(ans,x);}cnt[x] ++;// 移入计数}return ans;}
};
