Java实现技能差≤1的男女最大配对数问题代码错误排查

首先，咱们先明确这个问题的核心解法：排序+双指针，这是处理这类配对问题最高效的方式，时间复杂度能满足1e5的规模要求。我先给你分析可能出错的点，再给出正确的Java实现。

常见错误排查 #

你的代码只通过2/4测试用例，大概率是以下几个问题之一：

• 没有对技能数组排序：如果不排序，双指针的匹配逻辑完全失效，只能随机匹配，肯定会错过最优解。
• 双指针移动逻辑错误：比如当男生技能远小于女生时，应该移动男生指针，而不是女生指针；反之亦然。逻辑错了会导致配对数偏少。
• 输入处理不当：比如多测试用例时，没有重置指针、计数器等变量；或者读取数组时少读/多读了元素。
• 暴力解法超时：如果用了双重循环遍历所有男女组合，时间复杂度是O(N*M)，对于1e5的规模来说肯定会超时，过不了大测试用例。

正确的Java实现 #

下面是符合要求的代码，我会加上详细注释：

import java.io.*;
import java.util.*;

public class ChessPairing {
    public static void main(String[] args) throws IOException {
        // 用BufferedReader读取输入，避免大规模输入超时
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        
        while (T-- > 0) {
            // 读取男生数据
            int N = Integer.parseInt(br.readLine());
            int[] boys = new int[N];
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                boys[i] = Integer.parseInt(st.nextToken());
            }
            
            // 读取女生数据
            int M = Integer.parseInt(br.readLine());
            int[] girls = new int[M];
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < M; i++) {
                girls[i] = Integer.parseInt(st.nextToken());
            }
            
            // 排序是核心前提！没有排序双指针逻辑不成立
            Arrays.sort(boys);
            Arrays.sort(girls);
            
            int boyPtr = 0, girlPtr = 0, pairCount = 0;
            while (boyPtr < N && girlPtr < M) {
                int skillDiff = Math.abs(boys[boyPtr] - girls[girlPtr]);
                if (skillDiff <= 1) {
                    // 符合配对条件，两个指针都后移（元素已被使用）
                    pairCount++;
                    boyPtr++;
                    girlPtr++;
                } else if (boys[boyPtr] < girls[girlPtr]) {
                    // 当前男生技能太小，后面的女生技能更大，只能换个男生试试
                    boyPtr++;
                } else {
                    // 当前女生技能太小，后面的男生技能更大，换个女生试试
                    girlPtr++;
                }
            }
            
            System.out.println(pairCount);
        }
        br.close();
    }
}

代码关键说明 #

1. 输入优化：用BufferedReader+StringTokenizer替代Scanner，避免大规模输入时的超时问题。
2. 排序逻辑：对男女技能数组升序排序后，双指针才能按顺序匹配，保证每一步都能找到当前最优的配对，最终得到最大配对数。
3. 双指针移动规则：
   • 差值≤1时，配对成功，两个指针同时前进（因为这两个元素已经被占用）。
   • 男生技能更小：说明当前男生无法匹配任何后续女生（女生数组升序，后续技能只会更大），直接移动男生指针。
   • 女生技能更小：同理，移动女生指针。
4. 多测试用例隔离：每次循环都会重置指针和计数器，确保不同测试用例之间没有数据干扰。

你可以把这个代码和你的原代码对比，看看是不是犯了上面提到的错误，比如没排序或者指针逻辑出错了。

内容的提问来源于stack exchange，提问作者adnan ahmed