2080.区间内查询数字的频率

https://leetcode-cn.com/problems/range-frequency-queries/

每次query都直接遍历数组肯定超时

改变思路，用map存每个数字出现的位置

class RangeFreqQuery:

    def __init__(self, arr: List[int]):
        self.map = {}	# 数值为键，值为下标数组
        for i in range(len(arr)):
            if arr[i] not in self.map:
                self.map[arr[i]] = [i]
            else:
                # 因为是从头遍历，因此加入列表是有序的
                self.map[arr[i]].append(i)

    def query(self, left: int, right: int, value: int) -> int:
        if value not in self.map:
            return 0
        indexs = self.map[value]
        # 利用value的下标数组是有序的这个特性，二分找left、right在数组中的位置
        l = bisect_left(indexs, left)
        r = bisect_right(indexs, right)
        return r - l