哈希大法

枚举右，维护左

对于双变量问题，例如两数之和 (a_i + a_j = t)，可以枚举右边的 (a_j)，转换成单变量问题。也就是在 (a_j) 左边查找是否有 (a_i = t - a_j)，这可以用哈希表维护。

用哈希记录之前的数，并用于判断情况是否成立

二重哈希

第一个哈希的value被当作key放入第二个哈希

字符串哈希

请看字符串哈希

前缀和+哈希表

请看前缀和

遍历过程维护集合大小

在遍历的过程中，我们可以通过前后双指针（滑动窗口），动态维护一个哈希表，来确保当前窗口的元素集合大小不超过某个值k，如下代码所示

1
2
3
4
5
6
7
8
9
10
11
12
13
for (int i = 0, j = 0; i < n; i++) {  // 前后双指针+哈希表记录集合大小
    for (; j < n && map.size() <= k; j++) {
        if (map.size() == k && map.get(nums[j]) == null) break;  // 超过则退出循环
        map.merge(nums[j], 1, Integer::sum);
    }
    res += j - i;
    if (map.get(nums[i]) == 1) {
        map.remove(nums[i]);
    }
    else {
        map.merge(nums[i], -1, Integer::sum);
    }
}

找出唯一性数组的中位数

给你一个整数数组 nums 。数组 nums 的 唯一性数组 是一个按元素从小到大排序的数组，包含了 nums 的所有

非空子数组中

不同元素的个数。

换句话说，这是由所有 0 <= i <= j < nums.length 的 distinct(nums[i..j]) 组成的递增数组。

其中，distinct(nums[i..j]) 表示从下标 i 到下标 j 的子数组中不同元素的数量。

返回 nums 唯一性数组 的 中位数 。

注意，数组的 中位数 定义为有序数组的中间元素。如果有两个中间元素，则取值较小的那个。

示例 1：

**输入：**nums = [1,2,3]

**输出：**1

解释：

nums 的唯一性数组为 [distinct(nums[0..0]), distinct(nums[1..1]), distinct(nums[2..2]), distinct(nums[0..1]), distinct(nums[1..2]), distinct(nums[0..2])]，即 [1, 1, 1, 2, 2, 3] 。唯一性数组的中位数为 1 ，因此答案是 1 。

示例 2：

**输入：**nums = [3,4,3,4,5]

**输出：**2

解释：

nums 的唯一性数组为 [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3] 。唯一性数组的中位数为 2 ，因此答案是 2 。

示例 3：

**输入：**nums = [4,3,5,4]

**输出：**2

解释：

nums 的唯一性数组为 [1, 1, 1, 1, 2, 2, 2, 3, 3, 3] 。唯一性数组的中位数为 2 ，因此答案是 2 。

提示：

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^5

二分+（前后双指针+哈希表记录集合大小）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public int medianOfUniquenessArray(int[] nums) {
        int n = nums.length, l = 1, r = n;
        long len = (long)n*(n+1)/2, tg = (len+1)/2;
        while (l < r) {  // 二分
            int m = l + (r-l)/2;
            long cnt = calc(nums, m);  // 计算大小不超过m的集合个数
            if (cnt < tg) l = m+1;
            else r = m;
        }
        return l;
    }
    private long calc(int nums[], int k) {
        int n = nums.length;
        long res = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0, j = 0; i < n; i++) {  // 前后双指针+哈希表记录集合大小
            for (; j < n && map.size() <= k; j++) {
                if (map.size() == k && map.get(nums[j]) == null) break;  // 超过则退出循环
                map.merge(nums[j], 1, Integer::sum);
            }
            res += j - i;
            if (map.get(nums[i]) == 1) {
                map.remove(nums[i]);
            }
            else {
                map.merge(nums[i], -1, Integer::sum);
            }
        }
        return res;
    }
}