Leetcode 每日一题

mengnankkzhou2025-04-012025-04-20

4.1

给你一个下标从 0 开始的二维整数数组 questions ，其中 questions[i] = [pointsi, brainpoweri] 。

这个数组表示一场考试里的一系列题目，你需要 按顺序 （也就是从问题 0 开始依次解决），针对每个问题选择解决或者跳过操作。解决问题 i 将让你获得 pointsi 的分数，但是你将无法解决接下来的 brainpoweri 个问题（即只能跳过接下来的 brainpoweri 个问题）。如果你跳过问题 i ，你可以对下一个问题决定使用哪种操作。

比方说，给你
1
questions = [[3, 2], [4, 3], [4, 4], [2, 5]]
：
- 如果问题 0 被解决了，那么你可以获得 3 分，但你不能解决问题 1 和 2 。
- 如果你跳过问题 0 ，且解决问题 1 ，你将获得 4 分但是不能解决问题 2 和 3 。

请你返回这场考试里你能获得的最高分数。

class Solution101{
    public long mostPoints(int[][] questions){
        long[] memo = new long[questions.length];
        return dfs(0,questions,memo);
    }
    private long dfs(int i,int[][] questions,long[] memo){
        if (i>=memo.length){
            return 0;
        }
        if (memo[i]>0){
            return memo[i];
        }
        long notChoose  = dfs(i+1,questions,memo);
        long choose = dfs(i+questions[i][1]+1,questions,memo)+questions[i][0];
        return memo[i] = Math.max(notChoose,choose);
    }
}

questions [i][0}: 当前问题的分数。

questions[i][1}: 如果选择当前问题，你需要跳过接下来的 questions[i][1] 个问题。

4.2

有序三元组中的最大值 I

给你一个下标从 0 开始的整数数组 nums 。

请你从所有满足 i < j < k 的下标三元组 (i, j, k) 中，找出并返回下标三元组的最大值。如果所有满足条件的三元组的值都是负数，则返回 0 。

下标三元组 (i, j, k) 的值等于 (nums[i] - nums[j]) * nums[k] 。

两个变量 mx 和 mxDiff 分别维护前缀最大值和最大差值

ans维护答案；

class Solution102{
    public long maximumTripletValue(int[] nums){
        long ans = 0,mxDiff = 0;
        int mx = 0;
        for (int x:nums){
            ans = Math.max(ans,mxDiff*x);
            mxDiff = Math.max(mx-x,mxDiff);
            mx  = Math.max(mx,x);
        }
        return ans;
    }
}

4.3

有序三元组中的最大值 II

给你一个下标从 0 开始的整数数组 nums 。

请你从所有满足 i < j < k 的下标三元组 (i, j, k) 中，找出并返回下标三元组的最大值。如果所有满足条件的三元组的值都是负数，则返回 0 。

下标三元组 (i, j, k) 的值等于 (nums[i] - nums[j]) * nums[k] 。

class Solution103{
    public long maximumTripletValue(int[] nums){
        long ans = 0;
        int maxDiff = 0;
        int preMax = 0;
        for (int x:nums){
            ans = Math.max(ans,(long) maxDiff*x);
            maxDiff = Math.max(maxDiff,preMax-x);
            preMax = Math.max(preMax,x);
        }
        return ans;
    }
}

4.4

给你一个有根节点 root 的二叉树，返回它 最深的叶节点的最近公共祖先 。

回想一下：

叶节点 是二叉树中没有子节点的节点
树的根节点的深度为 0，如果某一节点的深度为 d，那它的子节点的深度就是 d+1
如果我们假定 A 是一组节点 S 的 最近公共祖先，S 中的每个节点都在以 A 为根节点的子树中，且 A 的深度达到此条件下可能的最大值。

class Solution104{
    public TreeNode lcaDeepestLeaves(TreeNode root){
        return dfs(root).getValue();
    }
    private Pair<Integer,TreeNode> dfs(TreeNode node){
        if (node==null){
            return new Pair<>(0,null);
        }
        Pair<Integer,TreeNode> left = dfs(node.left);
        Pair<Integer,TreeNode> right = dfs(node.right);
        if (left.getKey()>right.getKey()){
            return new Pair<>(left.getKey()+1,left.getValue());
        }
        if (left.getKey()<right.getKey()){
            return new Pair<>(right.getKey()+1,right.getValue());
        }
        return new Pair<>(left.getKey()+1,node);
    }
}

Integer代表节点的深度，TreeNode代表该节点的公共祖先

如果左子树的深度大于右子树，表示深度较大的叶子节点在左子树，返回 (left.getKey() + 1, left.getValue())。

如果右子树的深度大于左子树，表示深度较大的叶子节点在右子树，返回 (right.getKey() + 1, right.getValue())。

如果左、右子树深度相同，表示当前节点是深度最深的叶子节点的公共祖先，返回 (left.getKey(), node)。

递归的终止条件是node==null

返回深度为0，节点为null

4.5

找出所有子集的异或总和再求和

一个数组的 异或总和 定义为数组中所有元素按位 XOR 的结果；如果数组为空，则异或总和为 0 。

例如，数组 [2,5,6] 的 异或总和 为 2 XOR 5 XOR 6 = 1 。

给你一个数组 nums ，请你求出 nums 中每个子集的 异或总和 ，计算并返回这些值相加之和。

**注意：**在本题中，元素相同的不同子集应多次计数。

数组 a 是数组 b 的一个子集的前提条件是：从 b 删除几个（也可能不删除）元素能够得到 a 。

一般地，设 nums 所有元素的 OR 为 or，nums 的所有子集的异或和的总和为
$$
or⋅2^n−1
$$
or |=x等价于 or = or | x;。它的作用是把 or 变量的值与 x 进行按位或运算，然后把结果赋值回 or 变量。

class Solution105{
    public int subsetXORSum(int[] nums){
        int or = 0;
        for (int x:nums){
            or |=x;
        }
        return or<<(nums.length-1);
    }
}

4.6

最大整除子集

给你一个由 无重复 正整数组成的集合 nums ，请你找出并返回其中最大的整除子集 answer ，子集中每一元素对 (answer[i], answer[j]) 都应当满足：

answer[i] % answer[j] == 0 ，或
answer[j] % answer[i] == 0

如果存在多个有效解子集，返回其中任何一个均可。

class Solution106{
    public List<Integer> largestDivisibleSubset(int[] nums){
        Arrays.sort(nums);
        int n  = nums.length;
        int[] f = new int[n];
        Arrays.fill(f,1);
        int k =0;
        for (int i=0;i<n;i++){
            for (int j =0;j<i;j++){
                if (nums[i]%nums[j]==0){
                    f[i] = Math.max(f[i],f[j]+1);
                }
            }
            if (f[k]<f[i]){
                k=i;
            }

        }
        int m =f[k];
        List<Integer> ans = new ArrayList<>();
        for (int i =k;m>0;--i){
            if (nums[k]%nums[i]==0&&f[i]==m){
                ans.add(nums[i]);
                k=i;
                --m;
            }
        }
        return ans;
    }
}

我们先对数组进行排序，这样可以保证对于任意的 i<j，如果 nums[i] 可以整除 nums[j]，那么 nums[i] 一定在 nums[j] 的左边。

接下来，我们定义 f[i] 表示以 nums[i] 为最大元素的最大整除子集的大小，初始时 f[i]=1。

对于每一个 i，我们从左往右枚举 j，如果 nums[i] 可以被 nums[j] 整除，那么 f[i] 可以从 f[j] 转移而来，我们更新 f[i]=max(f[i],f[j]+1)。过程中，我们记录 f[i] 的最大值的下标 k 以及对应的子集大小 m。

这是i%j部分

最后，我们从 k 开始倒序遍历，如果 nums[k] 可以被 nums[i] 整除，且 f[i]=m，那么 nums[i] 就是一个整除子集的元素，我们将 nums[i] 加入答案，并将 m 减 1，同时更新 k=i。继续倒序遍历，直到 m=0。

这是j%i部分

4.7(x)

分割等和子集

给你一个 只包含正整数 的非空数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

class Solution{
    public boolean canPartition(int[] nums){
        int s= 0;
        for (int num:nums){
            s+=num;//总的和
        }
        if (s%2!=0){
            return false;
        }
        s/=2;
        int n = nums.length;
        boolean[][] f = new boolean[n+1][s+1];
        f[0][0] = true;
        for (int i =0;i<n;i++){
            int x = nums[i];
            for (int j =0;j<=s;j++){
                f[i+1][j] = j>=x&&f[i][j-x]||f[i][j];
            }
        }
        return f[n][s];
    }
}

我们需要判断是否能从 nums 选出若干个数，使它们的和等于 s / 2。

这里 f[i][j] 表示：

只使用 nums[0] ~ nums[i-1] 这 i 个元素，能否凑出 j。

状态转移方程：
$$
f[i+1][j]=(j≥x) and f[i][j−x] or f[i][j]
$$

选择当前元素 x：f[i][j-x] 必须为 true，即 j-x 之前能被凑出。
不选 x：直接继承 f[i][j] 的状态。

4.8

使数组元素互不相同所需的最少操作次数

给你一个整数数组 nums，你需要确保数组中的元素 互不相同 。为此，你可以执行以下操作任意次：

从数组的开头移除 3 个元素。如果数组中元素少于 3 个，则移除所有剩余元素。

**注意：**空数组也视作为数组元素互不相同。返回使数组元素互不相同所需的 最少操作次数

一般地，倒着遍历 nums，如果 nums[i] 之前遍历过，意味着下标在 [0,i] 中的元素都要移除，这一共有 i+1 个数。每次操作移除 3 个数，全部移除完，需要操作

class Solution{
    public int minimumOperations(int[] nums){
        Set<Integer> seen = new HashSet<>();
        for (int i=nums.length-1;i>=0;i--){
            if (!seen.add(nums[i])){//nums[i]在seen中
                return i/3+1;
            }
        }
        return 0;
    }
}

4.9

使数组的值全部为 K 的最少操作次数

给你一个整数数组 nums 和一个整数 k 。

如果一个数组中所有 严格大于 h 的整数值都相等，那么我们称整数 h 是 合法的 。

比方说，如果 nums = [10, 8, 10, 8] ，那么 h = 9 是一个合法整数，因为所有满足 nums[i] > 9 的数都等于 10 ，但是 5 不是合法整数。

你可以对 nums 执行以下操作：

选择一个整数 h ，它对于当前 nums 中的值是合法的。
对于每个下标 i ，如果它满足 nums[i] > h ，那么将 nums[i] 变为 h 。

你的目标是将 nums 中的所有元素都变为 k ，请你返回最少操作次数。如果无法将所有元素都变 k ，那么返回 -1

本质是计算不同元素个数

class Solution109{
    public int minOperations(int[] nums,int k){
        int min = Arrays.stream(nums).min().getAsInt();//获取最小值
        if (k>min){
            return -1;
        }//不存在
        int distinctCount = (int)Arrays.stream(nums).distinct().count();//记录不同数字个数
        return distinctCount-(k==min?1:0);//等于就1，不等就0
    }
}

4.10(x)

统计强大整数的数目

给你三个整数 start ，finish 和 limit 。同时给你一个下标从 0 开始的字符串 s ，表示一个正整数。

如果一个正整数 x 末尾部分是 s （换句话说，s 是 x 的后缀），且 x 中的每个数位至多是 limit ，那么我们称 x 是 强大的 。

请你返回区间 [start..finish] 内强大整数的 总数目 。

如果一个字符串 x 是 y 中某个下标开始（包括 0 ），到下标为 y.length - 1 结束的子字符串，那么我们称 x 是 y 的一个后缀。比方说，25 是 5125 的一个后缀，但不是 512 的后缀

class Solution {
    private String s;
    private String t;
    private Long[] f;
    private int limit;

    public long numberOfPowerfulInt(long start, long finish, int limit, String s) {
        this.s = s;
        this.limit = limit;
        t = String.valueOf(start - 1);
        f = new Long[20];
        long a = dfs(0, true);
        t = String.valueOf(finish);
        f = new Long[20];
        long b = dfs(0, true);
        return b - a;
    }

    private long dfs(int pos, boolean lim) {
        if (t.length() < s.length()) {
            return 0;
        }
        if (!lim && f[pos] != null) {
            return f[pos];
        }
        if (t.length() - pos == s.length()) {
            return lim ? (s.compareTo(t.substring(pos)) <= 0 ? 1 : 0) : 1;
        }
        int up = lim ? t.charAt(pos) - '0' : 9;
        up = Math.min(up, limit);
        long ans = 0;
        for (int i = 0; i <= up; ++i) {
            ans += dfs(pos + 1, lim && i == (t.charAt(pos) - '0'));
        }
        if (!lim) {
            f[pos] = ans;
        }
        return ans;
    }
}

4.11

统计对称整数的数目

给你两个正整数 low 和 high 。

对于一个由 2 * n 位数字组成的整数 x ，如果其前 n 位数字之和与后 n 位数字之和相等，则认为这个数字是一个对称整数。

返回在 [low, high] 范围内的 对称整数的数目

class Solution111{
    public int countSymmetricIntegers(int low,int high){
        int ans = 0;
        for (int x=low;x<=high;++x){
            ans +=f(x);
        }
        return ans;
    }
    private int f(int x){
        String s = ""+x;
        int n  = s.length();
        if (n%2==1){
            return 0;
        }
        int a=0,b=0;
        for (int i=0;i<n/2;++i){
            a +=s.charAt(i)-'0';
        }
        for (int i=n/2;i<n;++i){
            b +=s.charAt(i)-'0';
        }
        return a==b ?1:0;
    }

}

就是一个简单的枚举，先看是不是能被2整除，能就是1，不能就是0

然后分别遍历前面的和，和后面的和，看是不是想等

相等返回1不相等返回0

然后遍历【low,high]

返回ans这个和

4.12

统计好整数的数目

给你两个正整数 n 和 k 。

如果一个整数 x 满足以下条件，那么它被称为 k 回文整数。

x 是一个回文整数。
x 能被 k 整除。

如果一个整数的数位重新排列后能得到一个 k 回文整数 ，那么我们称这个整数为好整数。比方说，k = 2 ，那么 2020 可以重新排列得到 2002 ，2002 是一个 k 回文串，所以 2020 是一个好整数。而 1010 无法重新排列数位得到一个 k 回文整数。

请你返回 n 个数位的整数中，有多少个好整数。

注意，任何整数在重新排列数位之前或者之后 都不能 有前导 0 。比方说 1010 不能重排列得到 101 。

本质上计算的是「有重复元素的排列个数」。

class Solution112{
    public long countGoodIntegers(int n,int k){
        int[] factorial = new int[n+1];
        factorial[0]=1;
        for (int i =1;i<=n;i++){
            factorial[i]=factorial[i-1]*i;
        }//阶乘
        long ans = 0;
        Set<String> vis = new HashSet<>();//去重
        int base = (int)Math.pow(10,(n-1)/2);//前半部分的起始值
        for (int i=base;i<base*10;i++){
            String s = Integer.toString(i);
            s+=new StringBuilder(s).reverse().substring(n%2);//构造回文
            if (Long.parseLong(s)%k>0){
                continue;
            }
            char[] sortedS = s.toCharArray();
            Arrays.sort(sortedS);
            if (!vis.add(new String(sortedS))){
                continue;
            }//去重
            int[] cnt = new int[10];//次数
             for (char c:sortedS){
                 cnt[c-'0']++;
            }
             int res = (n-cnt[0])*factorial[n-1];//不能以0为开头，然后乘以(n-1)!
             for (int c:cnt){
                 res/=factorial[c];
             }//去掉重复数字
             ans+=res;
        }
        return ans;
    }
}

4.13

统计好数字的数目

我们称一个数字字符串是 好数字 当它满足（下标从 0 开始）偶数下标处的数字为偶数且奇数下标处的数字为质数（2，3，5 或 7）。

比方说，"2582" 是好数字，因为偶数下标处的数字（2 和 8）是偶数且奇数下标处的数字（5 和 2）为质数。但 "3245" 不是好数字，因为 3 在偶数下标处但不是偶数。

给你一个整数 n ，请你返回长度为 n 且为好数字的数字字符串总数。由于答案可能会很大，请你将它对 109 + 7 取余后返回 。

一个 数字字符串 是每一位都由 0 到 9 组成的字符串，且可能包含前导 0 。

这个好数字的定义是排序的来的

长度为n的数字，a为偶数下表的数量 a=[n/2]=[n+1/2] 一共五个偶数，02468

奇数下标的数量为b=[n/2] 一共4个质数2357

所以总个数为
$$
5
^a
4 ^
b
$$

所以代码为：

class Solution113{
    private static final int MOD = 1_000_000_007;
    public int countGoodNumbers(long n){
        return (int)(pow(5,(n+1)/2)*pow(4,n/2)%MOD);
    }
    private long pow(long x,long n){
        long res = 1;
        while (n>0){
            if ((n&1)>0){
                res = res*x%MOD;
            }
            x =x*x%MOD;
            n>>=1;
        }
        return res;
    }

}

其中注意取mod

4.14

统计好三元组

给你一个整数数组 arr ，以及 a、b 、c 三个整数。请你统计其中好三元组的数量。

如果三元组 (arr[i], arr[j], arr[k]) 满足下列全部条件，则认为它是一个 好三元组 。

0 <= i < j < k < arr.length
|arr[i] - arr[j]| <= a
|arr[j] - arr[k]| <= b
|arr[i] - arr[k]| <= c

其中 |x| 表示 x 的绝对值。

返回 好三元组的数量

class Solution114{
    public int countGoodTriplets(int[] arr,int a,int b,int c){
        int n = arr.length;
        int ans = 0;
        for (int i = 0;i<n;i++){
            for (int j=i+1;j<n;j++){
                for (int k=j+1;k<n;k++){
                    if (Math.abs(arr[i]-arr[j])<=a&&Math.abs(arr[j]-arr[k])<=b&&Math.abs(arr[i]-arr[k])<=c){
                        ans++;
                    }
                }
            }
        }
        return ans;
    }
}

不用多说，直接暴力破解遍历就可以

4.15

统计数组中好三元组数目

给你两个下标从 0 开始且长度为 n 的整数数组 nums1 和 nums2 ，两者都是 [0, 1, ..., n - 1] 的排列。

好三元组 指的是 3 个 互不相同 的值，且它们在数组 nums1 和 nums2 中出现顺序保持一致。换句话说，如果我们将 pos1v 记为值 v 在 nums1 中出现的位置，pos2v 为值 v 在 nums2 中的位置，那么一个好三元组定义为 0 <= x, y, z <= n - 1 ，且 pos1x < pos1y < pos1z 和 pos2x < pos2y < pos2z 都成立的 (x, y, z) 。

请你返回好三元组的 总数目 。

class Solution {
    int n;
    int[] tree = new int[100010]; 
    public long goodTriplets(int[] nums1, int[] nums2) {
        n = nums1.length;
        long ans = 0;
        // [4,0,1,3,2] -> [0,1,2,3,4]
        // [4,1,0,2,3] -> [0,2,1,4,3]
        // 左边小于当前数的数量[0,1,1,3,3]
        // 右边大于当前数的数量[4,2,2,0,0]
        // ans = sum(left[i] * right[i]);
        Map<Integer, Integer> num2idx = new HashMap<>();
        for (int i = 0; i < n; i++) {
            num2idx.put(nums1[i], i);
        }
        for (int i = 0; i < n; i++) {   // nums2  [4,1,0,2,3] -> [0,2,1,4,3]的过程
            nums2[i] = num2idx.get(nums2[i]);
        }//
        for (int i = 0; i < n; i++) {
            int l = query(nums2[i] + 1); // 树状数组查询 左边小于nums2[i]的数
            int t = i - l; // 左边大于nums2[i]的数
            int r = (n - nums2[i] - 1) - t; // 右边大于nums2[i]的数
            add(nums2[i] + 1, 1); 
            ans += 1L * l * r;
        }
        return ans;
    }


    int lowbit(int x) {
        return x & -x;
    }

    int query(int x) {
        int ans = 0;
        for (int i = x; i > 0; i -= lowbit(i)) ans += tree[i];
        return ans;
    }

    void add(int x, int u) {
        for (int i = x; i <= n; i += lowbit(i)) tree[i] += u;
    }
}

映射，将nums1映射到nums[2]上来

然后把 nums2 中的每个值变成它在 nums1 中的索引。

lowbit返回最低位的1

query返回前缀和

add在x的位置上加u

l 意思是小于nums2[i]的数，比当前元素小的数有几个出现在之前。

t 是左边大于当前值的数

r是右边大于nums2[i]的数

4.16

统计好子数组的数目

给你一个整数数组 nums 和一个整数 k ，请你返回 nums 中好子数组的数目。

一个子数组 arr 如果有至少 k 对下标 (i, j) 满足 i < j 且 arr[i] == arr[j] ，那么称它是一个好子数组。

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

如果窗口中有 c 个元素 x，再进来一个 x，会新增 c 个相等数对。
如果窗口中有 c 个元素 x，再去掉一个 x，会减少 c−1 个相等数对。

用一个哈希表 cnt 维护子数组（窗口）中的每个元素的出现次数，以及相同数对的个数 pairs

从小到大枚举子数组右端点 right。现在准备把 x=nums[right] 移入窗口，那么窗口中有 cnt[x] 个数和 x 相同，所以 pairs 会增加 cnt[x]。然后把 cnt[x] 加一。

相同的去掉一个x,窗口中会减少cnt[x]-1个相等对数，然后cnt[x]-1

再去移动左端点

当右端点固定在 right 时，左端点在 0,1,2,…,left−1 的所有子数组都是满足要求的，这一共有 left 个。

class Solution116{
    public long countGood(int[] nums,int k){
        long ans= 0;
        Map<Integer,Integer> cnt = new HashMap<>();
        int pairs= 0;
        int left = 0;
        for (int x:nums){
            int c = cnt.getOrDefault(x,0);
            pairs+=c;//jin
            cnt.put(x,c+1);
            while (pairs>=k){//至少k对
                x=nums[left];
                c= cnt.get(x);
                pairs -=(c-1);//chu
                cnt.put(x,c-1);
                left++;//右移动
            }
            ans+=left;
        }
        return ans;
    }
}

4.17

统计数组中相等且可以被整除的数对

给你一个下标从 0 开始长度为 n 的整数数组 nums 和一个整数 k ，请你返回满足 0 <= i < j < n ，nums[i] == nums[j] 且 (i * j) 能被 k 整除的数对 (i, j) 的数目。

直接暴力for循环枚举就行

class Solution117{
    public int countPairs(int[] nums,int k){
        int ans =0;
        for (int j=1;j<nums.length;++j){
            for(int i=0;i<j;++i){
                ans +=nums[i]==nums[j]&&(i*j%k)==0?1:0;
            }
        }
        return ans;
    }
}

$$
0 <= i < j < n
$$

根据这个条件确定for循环的边界，然后直接暴力破解就行

4.18

统计坏数对的数目

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

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

class Solution118{
    public long countBadPairs(int[] nums){
        int n = nums.length;
        long ans  = (long)n*(n-1)/2;
        Map<Integer,Integer> cnt = new HashMap<>();
        for (int i =0;i<n;i++){
            int x = nums[i]-i;
            int c = cnt.getOrDefault(x,0);
            ans -=c;
            cnt.put(x,c+1);
        }
        return ans;
    }
}

假设所有的对数都是坏对，那么总对数一共是n*(n-1)/2

可以把问题转化为，数组 nums[i] - i，然后统计这些值的频次

Map.getOrDefault(key, defaultValue)：

如果 key 存在，返回对应的值；
如果不存在，返回 defaultValue。

Map.put(key, value)：

如果 key 已存在，覆盖原值；
否则新增一项。

这样来统计次数

附带题目：

好数对的数目

给你一个整数数组 nums 。

如果一组数字 (i,j) 满足 nums[i] == nums[j] 且 i < j ，就可以认为这是一组 好数对 。

返回好数对的数目。

很简单，就是反过来就行

class Solution118a{
    public int numIdenticalPairs(int[] nums){
        int n = nums.length;
        int ans = 0;
        Map<Integer,Integer> cnt = new HashMap<>();
        for (int x:nums){
            int c = cnt.getOrDefault(x,0);
            ans+=c;
            cnt.put(x,c+1);
        }
        return ans;
    }
}

4.19

统计公平数对的数目

给你一个下标从 0 开始、长度为 n 的整数数组 nums ，和两个整数 lower 和 upper ，返回 公平数对的数目 。

如果 (i, j) 数对满足以下情况，则认为它是一个 公平数对 ：

0 <= i < j < n，且
lower <= nums[i] + nums[j] <= upper

class Solution119{
    public long countFairPairs(int[] nums,int lower, int upper){
        Arrays.sort(nums);
        long ans = 0;
        for (int j=0;j<nums.length;j++){
            int r = lowerBound(nums,j,upper-nums[j]+1);
            int l = lowerBound(nums,j,lower-nums[j]);
            ans += r-l;
        }
        return ans;
    }
    private int lowerBound(int[] nums,int right,int target){
        int left=-1;
        while (left+1<right){
            int mid = (left+right)>>>1;
            if (nums[mid]>=target){
                right=mid;
            }else {
                left=mid;
            }
        }
        return right;
    }
}

使用二分查找，最后target=right

lower <= nums[i] + nums[j] <= upper进行移项

1	注意要在 [0, j-1] 中二分，因为题目要求两个下标 i < j

因为不相等的话upper那个就要+1

lower-nums[i]

upper-nums[j]+1

最后两个数量相减的和就是对数，就是答案

4.20

781. 森林中的兔子

森林中有未知数量的兔子。提问其中若干只兔子 “还有多少只兔子与你（指被提问的兔子）颜色相同?” ，将答案收集到一个整数数组 answers 中，其中 answers[i] 是第 i 只兔子的回答。

给你数组 answers ，返回森林中兔子的最少数量。

class Solution120{
    public int numRabbits(int[] answers){
        int ans= 0;
        Map<Integer,Integer> left = new HashMap<>();
        for (int x:answers){
            int c = left.getOrDefault(x,0);
            if (c==0){
                ans+=x+1;
                left.put(x,x);
            }else {
                left.put(x,c-1);
            }
        }
        return ans;
    }
}