哈希表 – 第 4 页

1980.找出不同的二进制字符串

目标

给你一个字符串数组 nums ，该数组由 n 个互不相同的二进制字符串组成，且每个字符串长度都是 n 。请你找出并返回一个长度为 n 且没有出现在 nums 中的二进制字符串。如果存在多种答案，只需返回任意一个即可。

示例 1：

输入：nums = ["01","10"]
输出："11"
解释："11" 没有出现在 nums 中。"00" 也是正确答案。

示例 2：

输入：nums = ["00","01"]
输出："11"
解释："11" 没有出现在 nums 中。"10" 也是正确答案。

示例 3：

输入：nums = ["111","011","001"]
输出："101"
解释："101" 没有出现在 nums 中。"000"、"010"、"100"、"110" 也是正确答案。

说明：

n == nums.length
1 <= n <= 16
nums[i].length == n
nums[i] 为 '0' 或 '1'
nums 中的所有字符串互不相同

思路

有 n 个长度为 n 的二进制字符串数组，构造一个长度为 n 的字符串，使它与数组中的字符串不同，答案可能有多个返回任一一个即可。

康托对角线，构造字符串的第 i 个位置与 nums[i] 的第 i 个位置不同，这样可以保证构造出的字符串与数组中的所有字符串都不同。

代码


/**
 * @date 2026-03-09 18:08
 */
public class FindDifferentBinaryString1980 {

    public String findDifferentBinaryString_v1(String[] nums) {
        int n = nums.length;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            int c = nums[i].charAt(i) - '0';
            sb.append(c ^ 1);
        }
        return sb.toString();
    }

}

性能

1461.检查一个字符串是否包含所有长度为K的二进制子串

目标

给你一个二进制字符串 s 和一个整数 k 。如果所有长度为 k 的二进制字符串都是 s 的子串，请返回 true ，否则请返回 false 。

示例 1：

输入：s = "00110110", k = 2
输出：true
解释：长度为 2 的二进制串包括 "00"，"01"，"10" 和 "11"。它们分别是 s 中下标为 0，1，3，2 开始的长度为 2 的子串。

示例 2：

输入：s = "0110", k = 1
输出：true
解释：长度为 1 的二进制串包括 "0" 和 "1"，显然它们都是 s 的子串。

示例 3：

输入：s = "0110", k = 2
输出：false
解释：长度为 2 的二进制串 "00" 没有出现在 s 中。

说明：

1 <= s.length <= 5 * 10^5
s[i] 不是 '0' 就是 '1'
1 <= k <= 20

思路

检查一个二进制字符串是否包含所有长度为 k 的二进制子串。

长度为 k 的二进制子串的个数有 2^k 个，将子串视为二进制数字，使用长度为 k 的滑动窗口，记录窗口内子串表示的数字，判断是否所有数字都出现过即可。将左边界移出窗口需要将左边第一位置零 num = (num & (1 << (k - 1))) ^ num。先提取左边第一位，其余位均为 0，然后与 num 异或即可。

代码


/**
 * @date 2026-02-24 11:31
 */
public class HasAllCodes1461 {

    public boolean hasAllCodes(String s, int k) {
        if (k > 18) {
            return false;
        }
        int n = 1 << k;
        boolean[] visited = new boolean[n];
        int num = 0;
        char[] chars = s.toCharArray();
        int l = 0;
        for (int r = 0; r < chars.length; r++) {
            num = (num << 1) | (chars[r] - '0');
            if (r - l + 1 == k) {
                visited[num] = true;
                num = (num & (1 << (k - 1))) ^ num;
                l++;
            }
        }
        for (boolean b : visited) {
            if (!b) {
                return false;
            }
        }
        return true;
    }

}

性能

3714.最长的平衡子串II

目标

给你一个只包含字符 'a'、'b' 和 'c' 的字符串 s。

如果一个子串中所有不同字符出现的次数都相同，则称该子串为平衡子串。

请返回 s 的最长平衡子串的长度。

子串是字符串中连续的、非空的字符序列。

示例 1：

输入： s = "abbac"
输出： 4
解释：
最长的平衡子串是 "abba"，因为不同字符 'a' 和 'b' 都恰好出现了 2 次。

示例 2：

输入： s = "aabcc"
输出： 3
解释：
最长的平衡子串是 "abc"，因为不同字符 'a'、'b' 和 'c' 都恰好出现了 1 次。

示例 3：

输入： s = "aba"
输出： 2
解释：
最长的平衡子串之一是 "ab"，因为不同字符 'a' 和 'b' 都恰好出现了 1 次。另一个最长的平衡子串是 "ba"。

说明：

1 <= s.length <= 10^5
s 仅包含字符 'a'、'b' 和 'c'。

思路

定义平衡子串是字符出现次数相同的字符串，给定一个由 a b c 三种字符组成的字符串，返回最长的平衡子串长度。

// todo

代码

性能

3713.最长的平衡子串I

目标

给你一个由小写英文字母组成的字符串 s。

如果一个子串中所有不同字符出现的次数都相同，则称该子串为平衡子串。

请返回 s 的最长平衡子串的长度。

子串是字符串中连续的、非空的字符序列。

示例 1：

输入： s = "abbac"
输出： 4
解释：
最长的平衡子串是 "abba"，因为不同字符 'a' 和 'b' 都恰好出现了 2 次。

示例 2：

输入： s = "zzabccy"
输出： 4
解释：
最长的平衡子串是 "zabc"，因为不同字符 'z'、'a'、'b' 和 'c' 都恰好出现了 1 次。

示例 3：

输入： s = "aba"
输出： 2
解释：
最长的平衡子串之一是 "ab"，因为不同字符 'a' 和 'b' 都恰好出现了 1 次。另一个最长的平衡子串是 "ba"。

说明：

1 <= s.length <= 1000
s 仅由小写英文字母组成。

思路

定义平衡子串是字符出现次数相同的字符串，给定一个由小写英文字母组成的字符串，返回最长的平衡子串长度。

与 3719.最长平衡子数组I 类似，本题需要保证子串中字母出现的次数都相等，可以统计子串内字母的出现次数并判断是否完全相同。

在遍历的过程中，如何判断出现的字符是否都达到 k 个？字母种类数 * k 应当等于子串长度。

代码


/**
 * @date 2026-02-12 9:19
 */
public class LongestBalanced3713 {

    public int longestBalanced(String s) {
        int n = s.length();
        int res = 0;
        for (int i = 0; i < n; i++) {
            Map<Character, Integer> cnt = new HashMap<>();
            here:
            for (int j = i; j < n; j++) {
                char c = s.charAt(j);
                cnt.merge(c, 1, Integer::sum);
                int t = cnt.get(c);
                for (Integer value : cnt.values()) {
                    if (value != t) {
                        continue here;
                    }
                }
                res = Math.max(res, j - i + 1);
            }
        }
        return res;
    }
}

性能

3721.最长平衡子数组II

目标

给你一个整数数组 nums。

如果子数组中不同偶数的数量等于不同奇数的数量，则称该子数组是平衡的。

返回最长平衡子数组的长度。

子数组是数组中连续且非空的一段元素序列。

示例 1:

输入: nums = [2,5,4,3]
输出: 4
解释:
最长平衡子数组是 [2, 5, 4, 3]。
它有 2 个不同的偶数 [2, 4] 和 2 个不同的奇数 [5, 3]。因此，答案是 4 。

示例 2:

输入: nums = [3,2,2,5,4]
输出: 5
解释:
最长平衡子数组是 [3, 2, 2, 5, 4] 。
它有 2 个不同的偶数 [2, 4] 和 2 个不同的奇数 [3, 5]。因此，答案是 5。

示例 3:

输入: nums = [1,2,3,2]
输出: 3
解释:
最长平衡子数组是 [2, 3, 2]。
它有 1 个不同的偶数 [2] 和 1 个不同的奇数 [3]。因此，答案是 3。

说明:

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

提示:

Store the first (or all) occurrences for each value in pos[val].
Build a lazy segment tree over start indices l in [0..n-1] that supports range add and can tell if any index has value 0 (keep mn/mx).
Use sign = +1 for odd values and sign = -1 for even values.
Initialize by adding each value's contribution with update(p, n-1, sign) where p is its current first occurrence.
Slide left l: pop pos[nums[l]], let next = next occurrence or n, do update(0, next-1, -sign), then query for any r >= l with value 0 and update ans = max(ans, r-l+1).

思路

// todo

代码

性能

3719.最长平衡子数组I

目标

给你一个整数数组 nums。

如果子数组中不同偶数的数量等于不同奇数的数量，则称该子数组是平衡的。

返回最长平衡子数组的长度。

子数组是数组中连续且非空的一段元素序列。

示例 1:

输入: nums = [2,5,4,3]
输出: 4
解释:
最长平衡子数组是 [2, 5, 4, 3]。
它有 2 个不同的偶数 [2, 4] 和 2 个不同的奇数 [5, 3]。因此，答案是 4 。

示例 2:

输入: nums = [3,2,2,5,4]
输出: 5
解释:
最长平衡子数组是 [3, 2, 2, 5, 4] 。
它有 2 个不同的偶数 [2, 4] 和 2 个不同的奇数 [3, 5]。因此，答案是 5。

示例 3:

输入: nums = [1,2,3,2]
输出: 3
解释:
最长平衡子数组是 [2, 3, 2]。
它有 1 个不同的偶数 [2] 和 1 个不同的奇数 [3]。因此，答案是 3。

说明:

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

思路

定义平衡子数组是不同奇数元素个数与不同偶数元素个数相等的子数组，求数组 nums 的平衡子数组的最大长度。

暴力解法是枚举所有可能的子数组，判断是否是平衡子数组，即子数组中不相同奇数个数与不相同偶数个数是否相等。

无需针对每一个子数组都重新计数，考虑使用两个哈希表分别记录奇数元素与偶数元素的出现次数，判断哈希表中的 key 的个数是否相等即可。注意针对每一个起点，需要重新初始化哈希表。

代码


/**
 * @date 2026-02-10 9:16
 */
public class LongestBalanced3719 {

    public int longestBalanced(int[] nums) {
        int n = nums.length;
        int res = 0;
        for (int i = 0; i < n; i++) {
            Map<Integer, Integer>[] map = new HashMap[2];
            Arrays.setAll(map, x -> new HashMap<>());
            int l = nums[i] % 2;
            map[l].merge(nums[i], 1, Integer::sum);
            for (int j = i + 1; j < n; j++) {
                int r = nums[j] % 2;
                map[r].merge(nums[j], 1, Integer::sum);
                if (map[l].size() == map[l ^ 1].size()) {
                    res = Math.max(res, j - i + 1);
                }
            }
        }
        return res;
    }

}

性能

3013.将数组分成最小总代价的子数组II

目标

给你一个下标从 0 开始长度为 n 的整数数组 nums 和两个正整数 k 和 dist 。

一个数组的代价是数组中的第一个元素。比方说，[1,2,3] 的代价为 1 ，[3,4,1] 的代价为 3 。

你需要将 nums 分割成 k 个连续且互不相交的子数组，满足第二个子数组与第 k 个子数组中第一个元素的下标距离不超过 dist 。换句话说，如果你将 nums 分割成子数组 nums[0..(i1 - 1)], nums[i1..(i2 - 1)], ..., nums[ik-1..(n - 1)] ，那么它需要满足 ik-1 - i1 <= dist 。

请你返回这些子数组的最小总代价。

示例 1：

输入：nums = [1,3,2,6,4,2], k = 3, dist = 3
输出：5
解释：将数组分割成 3 个子数组的最优方案是：[1,3] ，[2,6,4] 和 [2] 。这是一个合法分割，因为 ik-1 - i1 等于 5 - 2 = 3 ，等于 dist 。总代价为 nums[0] + nums[2] + nums[5] ，也就是 1 + 2 + 2 = 5 。
5 是分割成 3 个子数组的最小总代价。

示例 2：

输入：nums = [10,1,2,2,2,1], k = 4, dist = 3
输出：15
解释：将数组分割成 4 个子数组的最优方案是：[10] ，[1] ，[2] 和 [2,2,1] 。这是一个合法分割，因为 ik-1 - i1 等于 3 - 1 = 2 ，小于 dist 。总代价为 nums[0] + nums[1] + nums[2] + nums[3] ，也就是 10 + 1 + 2 + 2 = 15 。
分割 [10] ，[1] ，[2,2,2] 和 [1] 不是一个合法分割，因为 ik-1 和 i1 的差为 5 - 1 = 4 ，大于 dist 。
15 是分割成 4 个子数组的最小总代价。

示例 3：

输入：nums = [10,8,18,9], k = 3, dist = 1
输出：36
解释：将数组分割成 4 个子数组的最优方案是：[10] ，[8] 和 [18,9] 。这是一个合法分割，因为 ik-1 - i1 等于 2 - 1 = 1 ，等于 dist 。总代价为 nums[0] + nums[1] + nums[2] ，也就是 10 + 8 + 18 = 36 。
分割 [10] ，[8,18] 和 [9] 不是一个合法分割，因为 ik-1 和 i1 的差为 3 - 1 = 2 ，大于 dist 。
36 是分割成 3 个子数组的最小总代价。

说明：

3 <= n <= 10^5
1 <= nums[i] <= 10^9
3 <= k <= n
k - 2 <= dist <= n - 2

思路

定义数组的代价是其第一个元素值，有一个数组 nums，将其分割成 k 个连续且不相交的子数组，并且要求第 2 个子数组与第 k 个子数组的第一个元素的下标的距离不超过 dist，求子数组的最小总代价。

//todo

代码

性能

3510.移除最小数对使数组有序II

目标

给你一个数组 nums，你可以执行以下操作任意次数：

选择相邻元素对中和最小的一对。如果存在多个这样的对，选择最左边的一个。
用它们的和替换这对元素。

返回将数组变为非递减所需的最小操作次数。

如果一个数组中每个元素都大于或等于它前一个元素（如果存在的话），则称该数组为非递减。

示例 1：

输入： nums = [5,2,3,1]
输出： 2
解释：
元素对 (3,1) 的和最小，为 4。替换后 nums = [5,2,4]。
元素对 (2,4) 的和为 6。替换后 nums = [5,6]。
数组 nums 在两次操作后变为非递减。

示例 2：

输入： nums = [1,2,2]
输出： 0
解释：
数组 nums 已经是非递减的。

说明：

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

提示：

We can perform the simulation using data structures.
Maintain an array index and value using a map since we need to find the next and previous ones.
Maintain the indices to be removed using a hash set.
Maintain the neighbor sums with the smaller indices (set or priority queue).
Keep the 3 structures in sync during the removals.

思路

代码

性能

3507.移除最小数对使数组有序I

目标

给你一个数组 nums，你可以执行以下操作任意次数：

选择相邻元素对中和最小的一对。如果存在多个这样的对，选择最左边的一个。
用它们的和替换这对元素。

返回将数组变为非递减所需的最小操作次数。

如果一个数组中每个元素都大于或等于它前一个元素（如果存在的话），则称该数组为非递减。

示例 1：

输入： nums = [5,2,3,1]
输出： 2
解释：
元素对 (3,1) 的和最小，为 4。替换后 nums = [5,2,4]。
元素对 (2,4) 的和为 6。替换后 nums = [5,6]。
数组 nums 在两次操作后变为非递减。

示例 2：

输入： nums = [1,2,2]
输出： 0
解释：
数组 nums 已经是非递减的。

说明：

1 <= nums.length <= 50
-1000 <= nums[i] <= 1000

思路

有一个数组 nums，每一次操作可以将数组中和最小的相邻元素用它们的和替换掉，求使得数组非递减所需要的最少操作次数。

暴力解法是每次遍历找到和最小的数对并替换，直到数组非递减。可以使用 next 数组模拟链表来删除元素。

代码


/**
 * @date 2026-01-22 9:02
 */
public class MinimumPairRemoval3507 {

    public int minimumPairRemoval_v1(int[] nums) {
        int res = 0;
        boolean decrease;
        int n = nums.length;
        int[] next = new int[n];
        Arrays.setAll(next, i -> i + 1);
        do {
            decrease = false;
            int index = 0, sum = Integer.MAX_VALUE;
            for (int i = 0; next[i] < n; i = next[i]) {
                if (nums[next[i]] < nums[i]) {
                    decrease = true;
                }
                int s = nums[i] + nums[next[i]];
                if (s < sum) {
                    sum = s;
                    index = i;
                }
            }
            if (decrease) {
                nums[index] = sum;
                next[index] = next[next[index]];
                res++;
            }
        } while (decrease);
        return res;
    }

}

性能

2975.移除栅栏得到的正方形田地的最大面积

目标

有一个大型的 (m - 1) x (n - 1) 矩形田地，其两个对角分别是 (1, 1) 和 (m, n) ，田地内部有一些水平栅栏和垂直栅栏，分别由数组 hFences 和 vFences 给出。

水平栅栏为坐标 (hFences[i], 1) 到 (hFences[i], n)，垂直栅栏为坐标 (1, vFences[i]) 到 (m, vFences[i]) 。

返回通过移除一些栅栏（可能不移除）所能形成的最大面积的正方形田地的面积，或者如果无法形成正方形田地则返回 -1。

由于答案可能很大，所以请返回结果对 10^9 + 7 取余后的值。

注意：田地外围两个水平栅栏（坐标 (1, 1) 到 (1, n) 和坐标 (m, 1) 到 (m, n) ）以及两个垂直栅栏（坐标 (1, 1) 到 (m, 1) 和坐标 (1, n) 到 (m, n) ）所包围。这些栅栏不能被移除。

示例 1：

输入：m = 4, n = 3, hFences = [2,3], vFences = [2]
输出：4
解释：移除位于 2 的水平栅栏和位于 2 的垂直栅栏将得到一个面积为 4 的正方形田地。

示例 2：

输入：m = 6, n = 7, hFences = [2], vFences = [4]
输出：-1
解释：可以证明无法通过移除栅栏形成正方形田地。

说明：

3 <= m, n <= 10^9
1 <= hFences.length, vFences.length <= 600
1 < hFences[i] < m
1 < vFences[i] < n
hFences 和 vFences 中的元素是唯一的。

思路

有一个 (m - 1) x (n - 1) 矩形田地，左上角坐标为 (1, 1)，右下角坐标为 (m, n)，田地内部有一些栅栏，水平栅栏 i 的纵坐标为 hFences[i]，垂直栅栏 j 的横坐标为 vFences[j]。可以移除一些栅栏，求能够形成的最大正方形的面积。

使用哈希表分别记录水平与垂直方向可能的间隔，找到最大相等间隔，相乘即可。

代码


/**
 * @date 2026-01-16 8:49
 */
public class MaximizeSquareArea2975 {

    public int maximizeSquareArea(int m, int n, int[] hFences, int[] vFences) {
        Set<Integer> hq = getInterval(m, hFences);
        Set<Integer> vq = getInterval(n, vFences);
        hq.retainAll(vq);
        if (hq.size() == 0) {
            return -1;
        }
        long res = 0;
        int mod = 1000000007;
        for (Integer num : hq) {
            res = Math.max(res, num);
        }
        return (int) (res * res % mod);
    }

    private Set<Integer> getInterval(int edge, int[] fences) {
        Arrays.sort(fences);
        Set<Integer> set = new HashSet<>();
        int n = fences.length;
        for (int i = 0; i < n; i++) {
            set.add(fences[i] - 1);
            set.add(edge - fences[i]);
            for (int j = i + 1; j < n; j++) {
                set.add(fences[j] - fences[i]);
            }
        }
        set.add(edge - 1);
        return set;
    }

}

2026 年 9 月
一	二	三	四	五	六	日
	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