标签： 计数

3442.奇偶频次间的最大差值I

目标

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

请你找出字符串中两个字符 a1 和 a2 的出现频次之间的 最大 差值 diff = a1 - a2，这两个字符需要满足：

  • a1 在字符串中出现 奇数次 。
  • a2 在字符串中出现 偶数次 。

返回 最大 差值。

示例 1：

输入：s = "aaaaabbc"
输出：3
解释：
字符 'a' 出现 奇数次 ，次数为 5 ；字符 'b' 出现 偶数次 ，次数为 2 。
最大差值为 5 - 2 = 3 。

示例 2：

输入：s = "abcabcab"
输出：1
解释：
字符 'a' 出现 奇数次 ，次数为 3 ；字符 'c' 出现 偶数次 ，次数为 2 。
最大差值为 3 - 2 = 1 。

说明：

  • 3 <= s.length <= 100
  • s 仅由小写英文字母组成。
  • s 至少由一个出现奇数次的字符和一个出现偶数次的字符组成。

思路

统计字符串中字符的出现频次，计算奇数频次最大值与偶数频次最小值的差。

代码


/**
 * @date 2025-06-10 8:42
 */
public class MaxDifference3442 {

    public int maxDifference(String s) {
        int[] cnt = new int[26];
        char[] chars = s.toCharArray();
        for (char c : chars) {
            cnt[c - 'a']++;
        }
        int oddMax = 0;
        int evenMin = Integer.MAX_VALUE;
        for (int i : cnt) {
            if (i == 0) {
                continue;
            }
            if (i % 2 == 1) {
                oddMax = Math.max(i, oddMax);
            } else {
                evenMin = Math.min(i, evenMin);
            }
        }
        return oddMax - evenMin;
    }
}

性能

1128.等价多米诺骨牌对的数量

目标

给你一组多米诺骨牌 dominoes 。

形式上，dominoes[i] = [a, b] 与 dominoes[j] = [c, d] 等价 当且仅当 (a == c 且 b == d) 或者 (a == d 且 b == c) 。即一张骨牌可以通过旋转 0 度或 180 度得到另一张多米诺骨牌。

在 0 <= i < j < dominoes.length 的前提下，找出满足 dominoes[i] 和 dominoes[j] 等价的骨牌对 (i, j) 的数量。

示例 1：

输入：dominoes = [[1,2],[2,1],[3,4],[5,6]]
输出：1

示例 2：

输入：dominoes = [[1,2],[1,2],[1,1],[1,2],[2,2]]
输出：3

说明：

  • 1 <= dominoes.length <= 4 * 10^4
  • dominoes[i].length == 2
  • 1 <= dominoes[i][j] <= 9

思路

计算二维数组中相同元素组成的下标对 (i, j) 个数，这里相同元素指 (dominoes[i][0] == dominoes[j][0] && dominoes[i][1] == dominoes[j][1]) || (dominoes[i][0] == dominoes[j][1] && dominoes[i][1] == dominoes[j][0])。

使用哈希表记录相同元素的出现次数，key 可以使用 dominoes[i][0] << 4 | dominoes[i][1] 和 dominoes[i][1] << 4 | dominoes[i][0] 表示。

代码


/**
 * @date 2025-05-04 17:38
 */
public class NumEquivDominoPairs1128 {

    public int numEquivDominoPairs(int[][] dominoes) {
        Map<Integer, Integer> map = new HashMap<>();
        int res = 0;
        for (int[] dominoe : dominoes) {
            int key = dominoe[0] << 4 | dominoe[1];
            res += map.getOrDefault(key, 0);
            map.merge(key, 1, Integer::sum);
            if (dominoe[0] != dominoe[1]) {
                map.merge(dominoe[1] << 4 | dominoe[0], 1, Integer::sum);
            }
        }
        return res;
    }

}

性能

2364.统计坏数对的数目

目标

给你一个下标从 0 开始的整数数组 nums 。如果 i < j 且 j - i != nums[j] - nums[i] ，那么我们称 (i, j) 是一个 坏数对 。

请你返回 nums 中 坏数对 的总数目。

示例 1：

输入：nums = [4,1,3,3]
输出：5
解释：数对 (0, 1) 是坏数对，因为 1 - 0 != 1 - 4 。
数对 (0, 2) 是坏数对，因为 2 - 0 != 3 - 4, 2 != -1 。
数对 (0, 3) 是坏数对，因为 3 - 0 != 3 - 4, 3 != -1 。
数对 (1, 2) 是坏数对，因为 2 - 1 != 3 - 1, 1 != 2 。
数对 (2, 3) 是坏数对，因为 3 - 2 != 3 - 3, 1 != 0 。
总共有 5 个坏数对，所以我们返回 5 。

示例 2：

输入：nums = [1,2,3,4,5]
输出：0
解释：没有坏数对。

说明：

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

思路

求数组中有多少坏数对，定义坏数对 (i, j) 满足 i < j && j - i != nums[j] - nums[i]。

将题目中的条件转化一下，j - nums[j] != i - nums[i]，可以维护一个 下标 - 元素值 数组。问题变为求当前下标前有多少个元素与当前元素 不同。对元素值计数，使用当前元素下标（表示 i 前的元素个数）减去当前元素值在前面的出现次数即可。

代码


/**
 * @date 2025-04-18 8:52
 */
public class CountBadPairs2364 {

    public long countBadPairs(int[] nums) {
        int n = nums.length;
        long res = 0L;
        Map<Integer, Long> cnt = new HashMap<>();
        for (int i = 0; i < n; i++) {
            res += i - cnt.merge(i - nums[i], 1L, Long::sum) + 1;
        }
        return res;
    }
}

性能

3185.构成整天的下标对数目II

目标

给你一个整数数组 hours，表示以 小时 为单位的时间，返回一个整数，表示满足 i < j 且 hours[i] + hours[j] 构成 整天 的下标对 i, j 的数目。

整天 定义为时间持续时间是 24 小时的 整数倍 。

例如，1 天是 24 小时，2 天是 48 小时，3 天是 72 小时，以此类推。

示例 1：

输入： hours = [12,12,30,24,24]
输出： 2
解释：
构成整天的下标对分别是 (0, 1) 和 (3, 4)。

示例 2：

输入： hours = [72,48,24,3]
输出： 3
解释：
构成整天的下标对分别是 (0, 1)、(0, 2) 和 (1, 2)。

说明：

  • 1 <= hours.length <= 5 * 10^5
  • 1 <= hours[i] <= 10^9

思路

有一个整数数组 hours，返回 hours[i] + hours[j] % 24 == 0，i < j 的下标对的个数。

与昨天的题目 3184.构成整天的下标对数目I 相比，数据规模从 100 变成了 5 * 10^5。枚举下标对的时间复杂度为 O(C(n,2))，即 O(n^2)，肯定会超时。

题目并不要求输出具体的下标对，只需要计数即可。当枚举右端点时，如果可以直接获取到已访问过的元素中，能够与当前元素组成合法下标对的元素个数，那么整体的时间复杂度可以降为 O(n)。定义 cnt[m] 表示已访问过的元素中对 24 取余后值为 m 的元素个数。当枚举到元素 i 时，只需累加 cnt[24 - nums[i] % 24] 即可。

代码


/**
 * @date 2024-10-23 10:16
 */
public class CountCompleteDayPairs3185 {

    public long countCompleteDayPairs_v2(int[] hours) {
        long res = 0L;
        int[] cnt = new int[24];
        int zeroCnt = 0;
        for (int hour : hours) {
            int m = hour % 24;
            if (m == 0) {
                res += zeroCnt;
                zeroCnt++;
            } else {
                res += cnt[24 - m];
                cnt[m]++;
            }
        }
        return res;
    }

}

性能