本文主要是介绍算法题技巧之“枚举右维护左“--套路详细讲解带例题和易懂代码(Python,C++)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
本文参考:
灵茶山艾府 - 力扣（LeetCode）
分享丨【题单】常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树） - 力扣（LeetCode）
本文主要讲解关于”枚举右维护左“这个刷算法题的技巧，包括简单的原理讲解和两个简单的例题(之后我也会总结一些这样的题目发题解在csdn上)，觉得有帮助或者写的不错可以点个赞
（最近刷到这种题挺多的，主要是在力扣上面遇到的，其他网站刷的少，暂时没遇到这种题目）
力扣的经典题”两数之和“就是使用的这个技巧
目录
原理讲解(例题一)：
原理：
实际例子讲解：
代码实现(C++):
代码实现（Python3）：
例题二：
题目大意和解题思路:
代码实现(C++):
代码实现(Python3):
原理讲解(例题一)：
. - 力扣（LeetCode）
原理：
通常有这么一个问题：要求满足题目条件的数对。比如例题一：如果一组数字 (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 = 0for x in nums:#可以在这里打印出哈希表的内容帮助理解#print(has)res += has.get(x, 0)has[x] = has.get(x, 0) + 1return res例题二：
. - 力扣（LeetCode）
题目大意和解题思路:
题目意思就是说，给你一个n行两列的二维数组，数组中每一行的两个元素分别表示一个矩形的长和宽，现在定义长和宽相比相同的矩形是 可互换的，现在让你求出给出的矩形中有多少是可互换的
当然可以暴力做：遍历两遍数组查找满足题目条件的情况：
以下是实现代码(Python):
class Solution:def interchangeableRectangles(self, nums: List[List[int]]) -> int:res = 0n = 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 += 1return 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 = 0for x in rectangles:res += has.get(x[0] / x[1], 0)has[x[0] / x[1]] = has.get(x[0] / x[1], 0) + 1return res这篇关于算法题技巧之“枚举右维护左“--套路详细讲解带例题和易懂代码(Python,C++)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
