标签： 双指针

目标

给你两个 非递增 的整数数组 nums1 和 nums2 ，数组下标均 从 0 开始 计数。

下标对 (i, j) 中 0 <= i < nums1.length 且 0 <= j < nums2.length 。如果该下标对同时满足 i <= j 且 nums1[i] <= nums2[j] ，则称之为 有效 下标对，该下标对的 距离 为 j - i 。

返回所有 有效 下标对 (i, j) 中的 最大距离 。如果不存在有效下标对，返回 0 。

一个数组 arr ，如果每个 1 <= i < arr.length 均有 arr[i-1] >= arr[i] 成立，那么该数组是一个 非递增 数组。

示例 1：

输入：nums1 = [55,30,5,4,2], nums2 = [100,20,10,10,5]
输出：2
解释：有效下标对是 (0,0), (2,2), (2,3), (2,4), (3,3), (3,4) 和 (4,4) 。
最大距离是 2 ，对应下标对 (2,4) 。

示例 2：

输入：nums1 = [2,2,2], nums2 = [10,10,1]
输出：1
解释：有效下标对是 (0,0), (0,1) 和 (1,1) 。
最大距离是 1 ，对应下标对 (0,1) 。

示例 3：

输入：nums1 = [30,29,19,5], nums2 = [25,25,25,25,25]
输出：2
解释：有效下标对是 (2,2), (2,3), (2,4), (3,3) 和 (3,4) 。
最大距离是 2 ，对应下标对 (2,4) 。

说明：

• 1 <= nums1.length <= 10^5
• 1 <= nums2.length <= 10^5
• 1 <= nums1[i], nums2[j] <= 10^5
• nums1 和 nums2 都是 非递增 数组

思路

有两个非递增的整数数组 nums1 和 nums2，返回有效下标对的最大距离，如果不存在有效下标对，返回 0。有效下标对 (i, j) 需要满足 i <= j && nums1[i] <= nums2[j]。

二分查找 nums2 大于等于 nums1[i] 的最大下标，记录 j - i 的最大值。

代码

/**
 * @date 2026-04-19 23:44
 */
public class MaxDistance1855 {

    public int maxDistance(int[] nums1, int[] nums2) {
        int res = 0;
        for (int i = 0; i < nums1.length; i++) {
            int j = upperBound(nums2, i, nums1[i]);
            res = Math.max(res, j - i);
        }
        return res;
    }

    public int upperBound(int[] arr, int l, int target) {
        int r = arr.length - 1;
        int m = l + (r - l) / 2;
        while (l <= r) {
            if (arr[m] >= target) {
                l = m + 1;
            } else {
                r = m - 1;
            }
            m = l + (r - l) / 2;
        }
        return r;
    }
}

性能

目标

一个数对 (a,b) 的 数对和 等于 a + b 。最大数对和 是一个数对数组中最大的 数对和 。

• 比方说，如果我们有数对 (1,5) ，(2,3) 和 (4,4)，最大数对和 为 max(1+5, 2+3, 4+4) = max(6, 5, 8) = 8 。

给你一个长度为 偶数 n 的数组 nums ，请你将 nums 中的元素分成 n / 2 个数对，使得：

• nums 中每个元素 恰好 在 一个 数对中，且
• 最大数对和 的值 最小 。

请你在最优数对划分的方案下，返回最小的 最大数对和 。

示例 1：

输入：nums = [3,5,2,3]
输出：7
解释：数组中的元素可以分为数对 (3,3) 和 (5,2) 。
最大数对和为 max(3+3, 5+2) = max(6, 7) = 7 。

示例 2：

输入：nums = [3,5,4,2,4,6]
输出：8
解释：数组中的元素可以分为数对 (3,5)，(4,4) 和 (6,2) 。
最大数对和为 max(3+5, 4+4, 6+2) = max(8, 8, 8) = 8 。

说明：

• n == nums.length
• 2 <= n <= 10^5
• n 是 偶数 。
• 1 <= nums[i] <= 10^5

思路

将长度为偶数的数组 nums 划分成若干数对，求这些数对和的最大值的最小值。

每种划分方案可以得到数对的最大值，取不同方案中最大值的最小值。

容易猜到划分方案应该是最小值与最大值组成数对，次小值与次大值组成数对，以此类推。

可以使用交换论证法来证明，如果存在一个更优的方案，那么可以通过 局部交换 操作，将其逐步调整为贪心方案，且每一步都不增加代价（或保持最优）。

代码

/**
 * @date 2026-01-26 11:32
 */
public class MinPairSum1877 {

    public int minPairSum(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        int res = 0;
        for (int i = 0; i < n / 2; i++) {
            res = Math.max(res, nums[i] + nums[n - 1 - i]);
        }
        return res;
    }

}

性能

目标

给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。

示例 1:

输入: nums = [2,2,3,4]
输出: 3
解释:有效的组合是: 
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3

示例 2:

输入: nums = [4,2,3,4]
输出: 4

说明:

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 1000

思路

有一个非负整数的数组，返回其中可以组成三角形的三元组。

可以先排序，然后使用二重循环，二分查找满足条件的第三边。

代码

/**
 * @date 2025-09-26 8:52
 */
public class TriangleNumber611 {

    public int triangleNumber(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        int res = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int t = nums[i] + nums[j];
                int index = bs(nums, j, t);
                res += Math.max(0, index - j);
            }
        }
        return res;
    }

    public int bs(int[] nums, int l, int target) {
        int r = nums.length - 1;
        int m = l + (r - l) / 2;
        while (l <= r) {
            if (nums[m] >= target) {
                r = m - 1;
            } else {
                l = m + 1;
            }
            m = l + (r - l) / 2;
        }
        return r;
    }

}

性能

目标

给你两个 版本号字符串 version1 和 version2 ，请你比较它们。版本号由被点 '.' 分开的修订号组成。修订号的值 是它 转换为整数 并忽略前导零。

比较版本号时，请按 从左到右的顺序 依次比较它们的修订号。如果其中一个版本字符串的修订号较少，则将缺失的修订号视为 0。

返回规则如下：

• 如果 version1 < version2 返回 -1，
• 如果 version1 > version2 返回 1，
• 除此之外返回 0。

示例 1：

输入：version1 = "1.2", version2 = "1.10"
输出：-1
解释：
version1 的第二个修订号为 "2"，version2 的第二个修订号为 "10"：2 < 10，所以 version1 < version2。

示例 2：

输入：version1 = "1.01", version2 = "1.001"
输出：0
解释：
忽略前导零，"01" 和 "001" 都代表相同的整数 "1"。

示例 3：

输入：version1 = "1.0", version2 = "1.0.0.0"
输出：0
解释：
version1 有更少的修订号，每个缺失的修订号按 "0" 处理。

说明：

• 1 <= version1.length, version2.length <= 500
• version1 和 version2 仅包含数字和 '.'
• version1 和 version2 都是 有效版本号
• version1 和 version2 的所有修订号都可以存储在 32 位整数 中

思路

比较两个由 . 分隔的版本号，每个由 . 隔开的部分称为修订号，从左到右分别比较对应的修订号，如果修订号缺失可认为是 0。如果 version1 > version2 返回 1，version1 < version2 返回 -1，否则返回 0。

使用 split 函数获取修订号，取二者修订号个数的最大值，初始化修订号为 0，如果修订号没有缺失则解析修订号，如果修订号不相等直接返回比较结果，否则继续比较下一个修订号。

代码

/**
 * @date 2025-09-23 8:49
 */
public class CompareVersion165 {

    public int compareVersion(String version1, String version2) {
        String[] v1 = version1.split("\\.");
        String[] v2 = version2.split("\\.");
        int n = Math.max(v1.length, v2.length);
        for (int i = 0; i < n; i++) {
            int i1 = 0;
            int i2 = 0;
            if (i < v1.length) {
                i1 = Integer.parseInt(v1[i]);
            }
            if (i < v2.length) {
                i2 = Integer.parseInt(v2[i]);
            }
            if (i1 > i2) {
                return 1;
            } else if (i1 < i2) {
                return -1;
            }
        }
        return 0;
    }
}

性能

目标

给你一个下标从 0 开始的整数数组 players ，其中 players[i] 表示第 i 名运动员的 能力 值，同时给你一个下标从 0 开始的整数数组 trainers ，其中 trainers[j] 表示第 j 名训练师的 训练能力值 。

如果第 i 名运动员的能力值 小于等于 第 j 名训练师的能力值，那么第 i 名运动员可以 匹配 第 j 名训练师。除此以外，每名运动员至多可以匹配一位训练师，每位训练师最多可以匹配一位运动员。

请你返回满足上述要求 players 和 trainers 的 最大 匹配数。

示例 1：

输入：players = [4,7,9], trainers = [8,2,5,8]
输出：2
解释：
得到两个匹配的一种方案是：
- players[0] 与 trainers[0] 匹配，因为 4 <= 8 。
- players[1] 与 trainers[3] 匹配，因为 7 <= 8 。
可以证明 2 是可以形成的最大匹配数。

示例 2：

输入：players = [1,1,1], trainers = [10]
输出：1
解释：
训练师可以匹配所有 3 个运动员
每个运动员至多只能匹配一个训练师，所以最大答案是 1 。

说明：

• 1 <= players.length, trainers.length <= 10^5
• 1 <= players[i], trainers[j] <= 10^9

思路

有两个数组 arr1 与 arr2，如果 arr1[i] <= arr2[j]，则称 arr1[i] 与 arr2[j] 相匹配。arr1 中的元素最多只能匹配一个 arr2 中的元素，同时，arr2 中的元素最多只能匹配一个 arr1 中的元素，求最大匹配数。

贪心策略，arr1 中的最小元素优先匹配 arr2 中的最小元素。

代码

/**
 * @date 2025-07-13 20:20
 */
public class MatchPlayersAndTrainers2410 {

    public int matchPlayersAndTrainers(int[] players, int[] trainers) {
        Arrays.sort(players);
        Arrays.sort(trainers);
        int m = players.length;
        int n = trainers.length;
        int res = 0;
        int i = 0, j = 0;
        while (i < m && j < n) {
            if (players[i] <= trainers[j]) {
                res++;
                i++;
            }
            j++;
        }
        return res;
    }

}

性能

目标

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

请你统计并返回 nums 中能满足其最小元素与最大元素的 和 小于或等于 target 的 非空 子序列的数目。

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

示例 1：

输入：nums = [3,5,6,7], target = 9
输出：4
解释：有 4 个子序列满足该条件。
[3] -> 最小元素 + 最大元素 <= target (3 + 3 <= 9)
[3,5] -> (3 + 5 <= 9)
[3,5,6] -> (3 + 6 <= 9)
[3,6] -> (3 + 6 <= 9)

示例 2：

输入：nums = [3,3,6,8], target = 10
输出：6
解释：有 6 个子序列满足该条件。（nums 中可以有重复数字）
[3] , [3] , [3,3], [3,6] , [3,6] , [3,3,6]

示例 3：

输入：nums = [2,3,3,4,6,7], target = 12
输出：61
解释：共有 63 个非空子序列，其中 2 个不满足条件（[6,7], [7]）
有效序列总数为（63 - 2 = 61）

说明：

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

思路

统计满足条件的子序列个数，要求子序列最小元素与最大元素之和小于等于 target。

排序后考虑首位元素组成的子序列，如果满足条件，那么有 2^n-1 个，将左指针右移继续判断，如果不满足条件，右指针左移继续判断。

代码

/**
 * @date 2025-06-30 10:47
 */
public class NumSubseq1498 {

    public int numSubseq(int[] nums, int target) {
        int mod = 1000000007;
        Arrays.sort(nums);
        if (nums[0] * 2 > target) {
            return 0;
        }
        int n = nums.length;
        int l = 0;
        int r = n - 1;
        int res = 0;
        while (l <= r) {
            if (nums[l] + nums[r] <= target) {
                res = (res + pow(2, r - l, mod)) % mod;
                l++;
            } else {
                r--;
            }
        }
        return res;
    }

    public int pow(int base, int exp, int mod) {
        long res = 1;
        while (exp > 0) {
            if ((exp & 1) == 1) {
                res = res * base % mod;
            }
            base = (int) (((long) base * base) % mod);
            exp >>= 1;
        }
        return (int) res;
    }

}

性能