本文参考:
分享丨【题单】常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树） - 力扣（LeetCode）
本文主要讲解关于”枚举右维护左“这个刷算法题的技巧，包括简单的原理讲解和两个简单的例题(之后我也会总结一些这样的题目发题解在csdn上)，觉得有帮助或者写的不错可以点个赞
（最近刷到这种题挺多的，主要是在力扣上面遇到的，其他网站刷的少，暂时没遇到这种题目）
力扣的经典题”两数之和“就是使用的这个技巧
目录
原理讲解(例题一)：
原理：
通常有这么一个问题：要求满足题目条件的数对。比如例题一：如果一组数字 (i,j) 满足 nums[i] == nums[j] 且 i < j ，就可以认为这是一组 好数对 。
通常的做法是遍历两遍数组，对于每一个数字，从这个数字开始遍历一遍数组，找出满足题目条件的数，但这样的做法时间复杂度为O(n^2),n为数组长度，遇到数据量多的时候会超时
那么就引出了”枚举右维护左“这个技巧
还是遍历数组，但是在遍历的过程中用一个哈希表存储已经查找过的元素，然后继续遍历，查看后面的元素和哈希表中已经存在的元素是否满足条件
实际例子讲解：
输入：nums = [1,2,3,1,1,3] 输出：4 解释：有 4 组好数对，分别是 (0,3), (0,4), (3,4), (2,5) ，下标从 0 开始
遍历数组
1存入hash，2存入hash，3存入hash，
现在遍历到1，此时hash里面有一个1, 那么此时满足好数对条件，答案加一，把此时的1再加入hash表
继续遍历，又是1，此时哈希表中有两个1，那么答案加2
继续遍历，是3，哈希表中有一个3，答案加1，最终答案是4
代码实现(C++):
class Solution {
public:
int numIdenticalPairs(vector<int>& nums) {
std::unordered_map<int, int> cnt;
int res = 0;
for (int i = 0; i < nums.size(); i++) {
res += cnt[nums[i]];
cnt[nums[i]]++;
}
return res;
}
};代码实现（Python3）：
class Solution:
def numIdenticalPairs(self, nums: List[int]) -> int:
has = {}
res = 0
for x in nums:
#可以在这里打印出哈希表的内容帮助理解
#print(has)
res += has.get(x, 0)
has[x] = has.get(x, 0) + 1
return res例题二：
题目大意和解题思路:
题目意思就是说，给你一个n行两列的二维数组，数组中每一行的两个元素分别表示一个矩形的长和宽，现在定义长和宽相比相同的矩形是 可互换的，现在让你求出给出的矩形中有多少是可互换的
当然可以暴力做：遍历两遍数组查找满足题目条件的情况：
以下是实现代码(Python):
class Solution:
def interchangeableRectangles(self, nums: List[List[int]]) -> int:
res = 0
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
if nums[i][0] / nums[i][1] == nums[j][0] / nums[j][1]:
res += 1
return res（题目n的范围是10^5,这个解法的复杂度是O(n^2), 暴力做就会超出时间限制）
此时就可以使用技巧”枚举右维护左“来解题，遍历数组，
把每一个长和宽的比值放入哈希表，然后在遍历的过程中查看是否有相同的情况
注意：
题目说：使用实数除法而非整数除法，那么需要哈希表的键的类型为double
代码实现(C++):
class Solution {
public:
long long interchangeableRectangles(vector<vector<int>>& rectangles) {
std::unordered_map<double, int> has;
long long res = 0;
for (auto& x : rectangles) {
double a = x[0], b = x[1];
res += has[a / b];
has[a / b]++;
}
return res;
}
};代码实现(Python3):
class Solution:
def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:
has = {}
res = 0
for x in rectangles:
res += has.get(x[0] / x[1], 0)
has[x[0] / x[1]] = has.get(x[0] / x[1], 0) + 1
return res