2021-05-15：数组为{3, 2, 2, 3, 1}，查询为(0, 3, 2)，意思是在数组里下标0~3这个范围上

2021-05-15：数组为{3, 2, 2, 3, 1}，查询为(0, 3, 2)，意思是在数组里下标0~3这个范围上，有几个2？答案返回2。假设给你一个数组arr， 对这个数组的查询非常频繁，都给出来。请返回所有查询的结果。

福大大 答案2021-05-15：

遍历存map。map的键是数组中的值，map的值是存数组下标的数组。比如{3,2,2,3,1}，保存到map里就是{3:[0,3],2:[0,1],1:[4]}，然后用二分法查找某个数的索引范围。

代码用golang编写。代码如下：

package main

import "fmt"

func main() {
    arr := []int{3, 2, 2, 3, 1}
    box := NewQueryBox2(arr)
    ret := box.query(0, 3, 2)
    fmt.Println(ret)
}

type QueryBox2 struct {
    dataMap map[int][]int
}

func NewQueryBox2(arr []int) *QueryBox2 {
    ret := &QueryBox2{}
    ret.dataMap = make(map[int][]int)
    for i := 0; i < len(arr); i++ {
        ret.dataMap[arr[i]] = append(ret.dataMap[arr[i]], i)
    }
    return ret
}

func (this *QueryBox2) query(L int, R int, value int) int {
    if _, ok := this.dataMap[value]; !ok {
        return 0
    }
    indexArr := this.dataMap[value]
    // 查询 < L 的下标有几个
    a := this.countLess(indexArr, L)
    // 查询 < R+1 的下标有几个
    b := this.countLess(indexArr, R+1)
    return b - a
}

// 在有序数组arr中，用二分的方法数出<limit的数有几个
// 也就是用二分法，找到<limit的数中最右的位置
func (this *QueryBox2) countLess(arr []int, limit int) int {
    L := 0
    R := len(arr) - 1
    mostRight := -1
    for L <= R {
        mid := L + ((R - L) >> 1)
        if arr[mid] < limit {
            mostRight = mid
            L = mid + 1
        } else {
            R = mid - 1
        }
    }
    return mostRight + 1
}

执行结果如下：

左神java代码