【Leetcode算题记录】枚举技巧(枚举右，维护左)

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。你可以按任意顺序返回答案。

这道题最直观的方法就是两重循环遍历所有可能的组合，时间复杂度是$O(n^2)$，采用枚举左，维护右的技巧可以将时间复杂度降为$O(n)$。题目要求找到一对下标满足$$nums[i]+nums[j]=target$$，那么可以将这个式子变型，也就是$nums[i]=target-nums[j]$，显然枚举右就是枚举每一个$$nums[j]$$并将下标一起保存到哈希表中，在$$nums[j]$$的左边查找是否存在$$nums[i]=target-nums[j]$$。

代码

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int,int> mp;
    for(int i=0;i<nums.size();i++){
        if(mp.find(target-nums[i])!=mp.end()){
            return {mp[target-nums[i]],i};
        }
        mp[nums[i]]=i;
    }
    return {};
}

这段代码中要注意的地方就是查找左边的数和将枚举右边的数加入哈希表的顺序，由于题目要求不能使用两次相同的元素，所以不能先将枚举右边的数加入哈希表中，不然在查找左边元素的时候就有可能使用到刚刚枚举的元素了。

给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。

📑枚举技巧，维护左枚举右

这道题采用维护左，枚举右的枚举技巧，在遍历数组nums的时候，用一个哈希表mp记录元素x上一次出现的位置，并在x的左边查找是否出现过且满足当前位置j和上一次出现的位置i(mp[nums[j]])的差满足题目条件。

bool containsNearbyDuplicate(vector<int>& nums, int k) {
    unordered_map<int,int> mp;
    for(int i=0;i<nums.size();i++){
        if(mp.contains(nums[i])&&i-mp[nums[i]]<=k){
            return true;
        }
        mp[nums[i]]=i;
    }
    return false;
}

这里同样要注意枚举右和维护左的顺序，题目要求了不同的索引，所以这里先在左边查找，再将枚举的右边元素加入到哈希表中。

除此之外，这道题还可以通过维护一个定长为k+1的滑动窗口解决。

对于一个长度为k+1的窗口，窗口中任意一个索引的差值的绝对值都不会超过k，那么我们就只需要遍历所有长度为k+1的窗口，判断窗口中是否存在重复元素即可。

具体操作就是用哈希集合维护窗口，从左到右遍历数组nums，当遍历到下标为i时：

1. 如果 i>k，则下标i−k−1处的元素被移出滑动窗口，因此将nums[i−k−1]从哈希集合中删除；
2. 判断 nums[i] 是否在哈希集合中，如果在哈希集合中则在同一个滑动窗口中有重复元素，返回 true，如果不在哈希集合中则将其加入哈希集合。

代码

bool containsNearbyDuplicate(vector<int>& nums, int k) {
    unordered_set<int> s;
    int n=nums.size();
    for(int i=0;i<n;i++){
        if(i>k){
            s.erase(nums[i-k-1]);
        }
        if(s.count(nums[i])){
            return true;
        }
        s.emplace(nums[i]);
    }
    return false;
}

给你一个整数数组 nums 。如果一组数字 (i,j) 满足 nums[i] == nums[j] 且 i < j ，就可以认为这是一组 好数对 。返回好数对的数目。

在遍历数组nums时，用哈希表cnt保存当前遍历过的每个数字及其出现的次数，对于每个元素nums[j]，其之前出现的次数即为与之构成好数对的数量，将这些数量累加到结果ans中，并更新nums[j]在哈希表cnt中的计数，最终返回累加的好数对总数ans。

int numIdenticalPairs(vector<int>& nums) {
    unordered_map<int,int>cnt;
    int ans=0;
    for(int i=0;i<nums.size();i++){
        ans+=cnt[nums[i]]++;

    }
    return ans;
}

代码中为什么先累加ans再更新哈希表？
如果先更新哈希表再累加好数对，那么我们在查看哈希表时得到的就是包括当前元素在内的总出现次数，这会导致我们将当前元素与自己也计算为一个好数对（即i == j的情况，但题目要求i < j），这不符合题目要求。

给你一个正整数数组 values，其中 values[i] 表示第 i 个观光景点的评分，并且两个景点 i 和 j 之间的 距离 为 j - i。一对景点（i < j）组成的观光组合的得分为 values[i] + values[j] + i - j ，也就是景点的评分之和 减去 它们两者之间的距离。

返回一对观光景点能取得的最高分。

得分$res=values[i]+values[j]+i-j$可以对这个式子稍加变一下型$res=(values[i]+i)+(values[j]-j)$对于这个式子，可以枚举j，同时维护在j左边$$values[i]+i$$的最大值left_max，用$$left\_max+values[j]-j$$来更新res的最大值。

int maxScoreSightseeingPair(vector<int>& values) {
    int left_max=INT_MIN,res=0;
    for(int i=0;i<values.size();i++){
        res=max(res,left_max+values[i]-i);
        left_max=max(left_max,i+values[i]);
    }
    return res;
}