# 1906. Minimum Absolute Difference Queries
###### tags: `Leetcode` `Medium` `Prefix Sum` `Binary Search`
Link: https://leetcode.com/problems/minimum-absolute-difference-queries/description/
## 思路
思路[参考](https://leetcode.com/problems/minimum-absolute-difference-queries/solutions/1284321/prefix-sums-vs-binary-search/)
注意constraint里面nums中所有数字最大不超过100
### Prefix Sum $O(100m+100n)$ $O(100n)$
m是queries的长度 n是nums的长度
cnt[i+1]表示nums[0:i]中每个数字的count
所以对于每一个query我们可以用cnt[query[1]+1]-cnt[query[0]]得到这query区间内所有数字的count
由此便可找到minimum absolute difference
由于这里面的minimum absolute difference不会等于0 所以cnt是几不重要 只要大于0就可以了
### Binary Search $O(n+100mlogn)$ $O(n)$
把每个数字出现的所有index记下来
对于每个query我们检查从1-100所有的数字 binary search看这个数字是否出现在query所表示的range里面
## Code
PrefixSum

class Solution {
    public int[] minDifference(int[] nums, int[][] queries) {
        int n = nums.length;
        int[][] cnt = new int[n+1][101];
        for(int i=0; i<n; i++){
            cnt[i+1] = cnt[i].clone();
            cnt[i+1][nums[i]]++;
        }
        int[] ans = new int[queries.length];
        for(int i=0; i<queries.length; i++){
            int prev = 0, diff = Integer.MAX_VALUE;
            for(int j=0; j<101; j++){
                if(cnt[queries[i][1]+1][j]-cnt[queries[i][0]][j]>0){
                    if(prev!=0) diff = Math.min(diff, j-prev);
                    prev = j;
                }
            }
            ans[i] = diff==Integer.MAX_VALUE?-1:diff;
        }
        return ans;
    }
}

Binary Search

class Solution {
    public int[] minDifference(int[] nums, int[][] queries) {
        List<List<Integer>> idx = new ArrayList<>();
        for(int i=0; i<=100; i++){
            idx.add(new ArrayList<>());
        }
        for(int i=0; i<nums.length; i++){
            idx.get(nums[i]).add(i);
        }
        int[] ans = new int[queries.length];
        for(int i=0; i<queries.length; i++){
            int a = queries[i][0];
            int b = queries[i][1];
            int diff = Integer.MAX_VALUE;
            int prev = 0;
            for(int j=0; j<=100; j++){
                int start = 0, end = idx.get(j).size();
                while(start<end){
                    int mid = start+(end-start)/2;
                    if(idx.get(j).get(mid)<a) start = mid+1;
                    else end = mid;
                }
                if(start<idx.get(j).size() && idx.get(j).get(start)<=b && idx.get(j).get(start)>=a){
                    if(prev!=0) diff = Math.min(diff, j-prev); 
                    prev = j;
                }
            }
            ans[i] = diff==Integer.MAX_VALUE?-1:diff;
        }
        return ans;
    }
}