剑指 Offer II 042. 最近请求次数

解题思路

解法1
1.二分查找，找到t的位置到t-3000的位置，然后求差
2.满足条件values.get(mid) >= t - 3000 && values.get(mid - 1) < t -3000时，此时即为满足条件的位置
3.注意：mid很有可能为0，此时不需要判断mid-1

解题遇到的问题

用链表和hash会超时，自己用数组，可以解决超时问题

后续需要总结学习的知识点

是否有其他解法？

##解法1
class RecentCounter {
    int[] values;
    int currentIndex = -1;

    public RecentCounter() {
        values = new int[10000];
        currentIndex = -1;
    }

    public int ping(int t) {
        currentIndex++;
        values[currentIndex] = t;
        int l = 0, r = currentIndex;
        // 二分查找，找到t的位置到t-3000的位置，然后求差
        while (l <= r) {
            int mid = (r - l) / 2 + l;
            // 满足条件values.get(mid) >= t - 3000 && values.get(mid - 1) < t -
            // 3000时，此时即为满足条件的位置
            if (values[mid] >= t - 3000) {
                // 注意：mid很有可能为0，此时不需要判断mid-1
                if (mid != 0) {
                    if (values[mid - 1] < t - 3000) {
                        return currentIndex - mid + 1;
                    } else {
                        r = mid - 1;
                    }
                } else {
                    return currentIndex - mid + 1;
                }
            } else {
                l = mid + 1;
            }
        }
        return 0;
    }
}