最近给团队做Java基础培训又把一道经典老题翻了出来两个乒乓球队比赛甲队a、b、c乙队x、y、z已经抽签决定了比赛名单。a说他不和x比c说他不和x、z比要求编程序找出完整的对阵名单。这道题在Java入门教材里出现频率极高也常被放进java面试题、蓝桥杯热身题里当逻辑题考。很多人第一次看到它时觉得无从下手其实它考察的并不是什么高深算法而是最基本的循环枚举能力以及把一句中文约束翻译成代码的功夫。这篇文章我就用Java把这道题完整拆一遍从最直观的暴力枚举到更适合扩展的全排列解法再到如何把题目里的约束条件抽象成可复用的代码结构。不管你是刚学到循环和数组的初学者还是准备面试想找点逻辑题手感的开发者应该都能从中拿到一些能直接用的东西。1. 为什么这道Java入门题能火这么多年先动手推一遍答案1.1 手工推导先知道答案再写代码拿到题先别急着敲键盘我习惯先把答案在草稿纸上推出来。把约束条件列清楚a的对手不是xc的对手不是x也不是za、b、c三个人的对手分别是x、y、z中的一个人且互不重复。因为c不能打x也不能打z乙队里只剩y所以c的对手必然是y。再看aa不能打x而y已经分给了c那么a能在x和z里选排除掉x之后只能打z。剩下b没得选对手就是x。结论a对zb对xc对y。手工推导最大的好处是你提前知道了预期答案写代码时就有了对照。程序跑出来如果和推导结果不一致说明代码有bug可以立刻回头检查如果一致就能放心往下走。这个先推答案再写代码的习惯在刷题和做业务需求时都很有用。1.2 它到底在考什么循环、条件、逻辑三件套仔细拆这道题它其实包含了三个层次。第一层是读懂规则。a说不和x比、c说不和x和z比这是显式约束三个人必须分别对应三个不同的对手这是隐式约束。很多人会忽略隐式约束导致枚举出来的组合里出现a和b都打x这种荒谬结果。第二层是把约束转成逻辑表达式。比如a不和x比在代码里就是对手 ! xc不和x、z比就是对手 ! x 对手 ! z。这一步考验的是把自然语言精确翻译成程序条件的能力翻译错了程序不会报错只会给出错误答案这是最让人头疼的。第三层是用循环把所有可能的组合都枚举一遍留下满足约束条件的组合。程序不会像人一样做演绎推理它的强项是遍历所以我们的思路应该是把所有排列列出来再筛选。很多初学者卡在第二层到第三层的转换上原因在于总想让程序像人一样思考。但程序没有常识它只认条件和循环。这正是编程思维和日常思维的典型差异人脑擅长演绎程序擅长遍历你要做的就是把演绎过程翻译成遍历加过滤。1.3 为什么一道乒乓球队题能长期出现在面试列表里网上关于java面试题、java基础、蓝桥杯的热搜常年不断这道乒乓球队题也是其中的熟面孔。它之所以经典不是因为它难而是因为它把三个核心能力浓缩在一个小题里逻辑澄清、条件表达、循环遍历。这三个能力恰恰是写业务代码时每天都要用的。打个比方真实系统里的排班匹配是多个员工排多个班次某些员工不能排某些班权限分配是多个角色分配多个资源某些角色不能访问某些资源本质上都是多对多匹配约束过滤和这道乒乓球队题的抽象结构完全一样。所以从学习角度讲认真吃透这道小题目比背一堆面试八股文要实在得多。2. 三重循环暴力枚举最直观写法的完整拆解2.1 最直觉的解法三层循环枚举所有组合第一种解法也是大多数教材里给出的写法就是三重循环。思路非常简单a、b、c各自的对手都从x、y、z里选三层循环把所有组合枚举一遍。组合总数量是3×3×327组然后筛掉重复对手的再筛掉违反约束条件的剩下的就是答案。这里有个关键点三层循环会允许两个人选到同一个对手所以必须先做去重判断。比如a选x、b也选x、c选y这种组合在现实里不可能出现因为一个人不可能同时跟两个人比赛。去重之后剩下的组合再继续检查约束条件。2.2 用下标而不是字母做循环变量写代码时有一个小细节很容易被忽略循环变量最好用下标而不是直接用字符。什么意思呢把乙队x、y、z放进一个数组char[] teamB {x, y, z}然后循环变量i、j、k分别表示a、b、c的对手在数组中的下标。这样做的好处是去重判断写起来非常干净三个人对手不同就是i ! j i ! k j ! k。如果用字符直接做循环变量也不是不行但去重要写成aOpp ! bOpp aOpp ! cOpp bOpp ! cOpp变量名一多新手容易看晕。用下标还有一个额外好处从数组里拿对手时写teamB[i]可以顺便用i做其他索引运算后面扩展N对N时思路更顺。2.3 代码逐行解读和运行结果验证完整代码如下public class PingPongMatch { public static void main(String[] args) { char[] teamA {a, b, c}; char[] teamB {x, y, z}; // i对应a的对手下标j对应b的对手下标k对应c的对手下标 for (int i 0; i teamB.length; i) { for (int j 0; j teamB.length; j) { for (int k 0; k teamB.length; k) { // 隐式约束三个人的对手不能重复 if (i j || i k || j k) { continue; } // 显式约束a不打xc不打x也不打z if (teamB[i] ! x teamB[k] ! x teamB[k] ! z) { System.out.println(teamA[0] vs teamB[i]); System.out.println(teamA[1] vs teamB[j]); System.out.println(teamA[2] vs teamB[k]); } } } } } }运行结果a vs z b vs x c vs y和手工推导完全一致。代码里没有显式判断b的约束因为题目本来就没给b的限制b只要有对手、且对手不跟a和c重复就行。如果某天题目加一句b也不和y比只需要在if条件里补一个teamB[j] ! y其余都不用动。2.4 用字符直接循环的另一种写法有些教材里会这么写逻辑一样只是变量直接存字符。我把两种写法都放出来方便你对比着看public class PingPongMatchChar { public static void main(String[] args) { char[] teamB {x, y, z}; for (char aOpp : teamB) { for (char bOpp : teamB) { for (char cOpp : teamB) { if (aOpp bOpp || aOpp cOpp || bOpp cOpp) { continue; } if (aOpp ! x cOpp ! x cOpp ! z) { System.out.println(a vs aOpp); System.out.println(b vs bOpp); System.out.println(c vs cOpp); } } } } } }两种写法跑出来的结果完全一致。我个人更喜欢下标写法因为后续如果要改成甲队也是动态输入下标方式更接近真实业务的索引操作习惯但字符写法也有优势就是逻辑更直观读代码的人不需要去数组里查下标。3. 全排列加回溯比三层循环更高级的解法3.1 为什么要把六种排列显式地列出来三重循环虽然能解但有个明显的笨拙感它在枚举27种组合然后靠去重这个条件把不符合一人对一个的组合扔掉。可实际上三个对手分给三个队员合法的排列一共只有6种。换个思路固定甲队顺序为a、b、c问题就变成了把x、y、z这3个对手排成一排第1个给a第2个给b第3个给c然后检查约束条件。这本质上是一个全排列问题。全排列是有通用解法的比写死三层循环更接近人脑的思考方式也更利于扩展到更多人数。3.2 交换法生成排列的完整代码生成全排列最经典的写法之一是交换法也叫回溯法。核心思想是一个坑一个坑地填填到最后一个坑时检查约束不满足就回退换一个候选继续试。public class MatchPermutation { private static char[] teamB {x, y, z}; public static void main(String[] args) { permute(0); } // start表示当前在确定第start个位置 // 位置0对应a的对手位置1对应b的对手位置2对应c的对手 private static void permute(int start) { if (start teamB.length - 1) { checkAndPrint(); return; } for (int i start; i teamB.length; i) { swap(start, i); permute(start 1); swap(start, i); // 回溯恢复现场 } } private static void checkAndPrint() { if (teamB[0] ! x teamB[2] ! x teamB[2] ! z) { System.out.println(a vs teamB[0]); System.out.println(b vs teamB[1]); System.out.println(c vs teamB[2]); } } private static void swap(int i, int j) { char tmp teamB[i]; teamB[i] teamB[j]; teamB[j] tmp; } }运行结果同样是a vs z b vs x c vs y3.3 递归里关键的一步为什么交换后还要交换回来这段代码里最容易让人困惑的是swap(start, i)之后的第二次swap。为什么递归返回后还要再交换一次因为数组是共享的。permute(0)进来后把teamB[0]依次和teamB[0]、teamB[1]、teamB[2]交换然后递归处理后面的位置。递归返回后如果不把数组恢复成交换前的样子下一轮循环里操作的就是已经被打乱的数组排列会乱结果会出现大量重复甚至漏解。递归前修改状态、递归后还原状态这个模式就是回溯法名字的由来。它不止出现在排列生成里还广泛出现在走迷宫、八皇后、数独这类问题上。你甚至可以把它理解成一个试错再回头的过程先假设这条路走得通走到头发现不行就退回来换一条路。第二次swap就是在退回来。3.4 三重循环和全排列回溯的对比我把两种写法放在一起比较一下方便你根据场景选型维度三重循环全排列回溯枚举数量27种组合包含重复6种排列天然不重复去重逻辑需要写ij之类的判断排列生成过程自带去重扩展性每加一个队员就要多一层循环循环层数由递归深度决定代码可读性直观但条件多了容易乱结构清晰约束集中在一个方法里适用规模3对3以内可以推广到n对n如果只是解这道题三重循环完全够用。但一旦题目变成两队各出5人三重循环的写法直接失效因为你需要写五层for循环而回溯法的递归深度是动态的几乎不用改代码结构。这也是我在实际刷题和带新人时更推荐掌握全排列思路的原因——它不是炫技是给未来留了一条更容易扩展的路。4. 别把规则写死在if里约束抽象才是这道题的精华4.1 把条件写死在if里短期省事长期吃亏回到工程视角。上面两版代码都能正确跑出答案但从代码维护的角度看它们有一个共同问题约束条件是直接写在if语句里的。题目说a不打x、c不打x和z代码里就写teamB[i] ! x teamB[k] ! x teamB[k] ! z。如果明天规则变成a不打y、b不打z你得记得回来改这一行。在小题目里这无所谓但在真实项目里这种散落在代码各处的业务规则是最难维护的。改规则的时候漏改一处系统就会在某个意想不到的地方给出错误结果。4.2 约束的另一种组织方式数据驱动判断更工程化的做法是把约束从代码里抽出来变成数据。比如用Map记录每个甲队队员的禁打对手集合再用一个统一的isValid方法去判断import java.util.*; public class MatchWithRules { public static void main(String[] args) { char[] teamB {x, y, z}; // 约束数据化a禁打xc禁打x和z MapCharacter, SetCharacter forbidden new HashMap(); forbidden.put(a, new HashSet(Arrays.asList(x))); forbidden.put(c, new HashSet(Arrays.asList(x, z))); for (char aOpp : teamB) { for (char bOpp : teamB) { for (char cOpp : teamB) { if (aOpp bOpp || aOpp cOpp || bOpp cOpp) { continue; } if (isValid(a, aOpp, forbidden) isValid(b, bOpp, forbidden) isValid(c, cOpp, forbidden)) { System.out.println(a vs aOpp); System.out.println(b vs bOpp); System.out.println(c vs cOpp); } } } } } private static boolean isValid(char player, char opponent, MapCharacter, SetCharacter forbidden) { SetCharacter bans forbidden.getOrDefault(player, Collections.emptySet()); return !bans.contains(opponent); } }运行结果不变还是a对z、b对x、c对y。但代码结构已经变了以后新增规则只需往forbidden这个Map里塞一条数据isValid方法不用动。这就是规则与逻辑分离的雏形。提示这种数据驱动思路不仅在算法题里有用业务系统里做配置中心、规则引擎本质上都是把经常变化的业务规则从硬编码中剥离出去让规则变成可配置的数据。早点养成这个习惯对写生产代码帮助很大。4.3 面试现场这道题的加分答法如果面试官现场出这道题我建议按这个顺序表达先说一下约束条件a、b、c的对手互不相同a不打xc不打x也不打z。然后说思路固定甲队顺序枚举乙队的全排列用约束条件过滤。写代码时把排列生成和约束检查分成两个方法代码结构干净。最后补一句复杂度3对3时其实只有6种排列如果扩展到n对n全排列规模是n的阶乘可以用回溯加剪枝优化。很多候选人一上来就写三重循环也不是不行但如果你能主动提到全排列回溯剪枝这几个词并且在代码里把约束管理做得清晰那肯定比闷头写循环的人高一个档次。面试官看的不只是正确结果更是你的思维方式和代码组织习惯。4.4 配对加约束过滤在真实系统里长什么样说实话这种逻辑题在实际开发里很少以乒乓球队比赛的形式出现但它的抽象原型到处都是。会议室排期多个会议抢多个时段某些会议不能占用某些时段任务分配多个开发者领多个需求某些开发者因为技术栈原因不能碰某些模块医院排班多个医生排多个班次有职称、出诊日、休假等约束。它们本质都是配对约束过滤和这道乒乓球队题是同一个模子刻出来的。理解了这一层你就会明白为什么面试官喜欢拿这类题试水题目本身不难但它能看出一个人有没有从暴力写死规则升级到抽象约束、数据驱动的工程意识。5. 从3对3到N对N回溯模板和约束满足问题入门5.1 三层循环写法的上限在哪里题目只给了3对3那如果变成两个乒乓球队各出5人三重循环还能用吗答案是不能。因为你需要写五层for循环代码瞬间变成灾难现场。即使硬写出五层循环一旦人数变成10人、20人循环层数直接失控。所以当我们想把这个解法推广到任意人数时必须把循环层数换成递归深度。递归的层数是动态的数组有多少人递归就下探多少层代码本身不用改。5.2 通用回溯模板n对n也能跑下面这个模板就是为一般情况准备的。固定甲队为a、b、c、d……用schedule数组记录当前已确定的配对用used数组标记乙队队员是否已经被分配。递归每层填一个坑时先做约束检查不过就剪掉这个分支。public class NMatch { // 乙队队员可以按题意改成任意多个 private static char[] teamB {v, w, x, y, z}; private static char[] schedule; private static boolean[] used; public static void main(String[] args) { schedule new char[teamB.length]; used new boolean[teamB.length]; backtrack(0); } private static void backtrack(int depth) { if (depth teamB.length) { // 所有坑都填满了输出结果 for (int i 0; i depth; i) { System.out.println((char) (a i) vs schedule[i]); } System.out.println(---); return; } for (int i 0; i teamB.length; i) { if (used[i]) { continue; } // 剪枝当前这个候选人如果违反约束直接跳过 if (!isValidSoFar(depth, teamB[i])) { continue; } used[i] true; schedule[depth] teamB[i]; backtrack(depth 1); used[i] false; // 回溯 } } // 按题目要求填约束 private static boolean isValidSoFar(int depth, char opponent) { // 示例第0个人(a)不打x第2个人(c)不打x和z if (depth 0 opponent x) { return false; } if (depth 2 (opponent x || opponent z)) { return false; } return true; } }这个模板已经不再受3对3的限制。题目变成5人、8人只需要改teamB数组以及isValidSoFar里的约束条件。代码结构一个字都不用变。5.3 剪枝的价值从4亿次枚举到几万次剪枝是什么就是明知道这条路走不通就不往下走了。在通用回溯模板里剪枝体现在isValidSoFar这个判断每填一个坑先检查当前这个配对是否已经违反约束破坏了就直接continue不进入下一层递归。不剪枝的话n对n要枚举n的阶乘个排列。n等于8时是40320个看起来不多n等于12时就到了4.79亿个普通程序已经跑不动了。加了剪枝之后很多分支在填到第三四个坑时就被砍掉实际遍历数量会少好几个数量级。这也是写对和写得有效率之间的关键差距。5.4 从这道题到约束满足问题到了这一步你已经不知不觉接触到约束满足问题的雏形了。约束满足问题Constraint Satisfaction ProblemCSP的核心三要素是变量、值域、约束。在这道题里变量是a、b、c各自的对手值域都是{x, y, z}约束是三个对手互不相同加上a不打x、c不打x和z。真实世界中的排课表、物流调度、游戏AI解谜、推荐系统里的组合过滤很多问题都可以建模成CSP去求解。理解了这道小题目以后再看到约束满足这个词你就不会觉得它是个玄乎的名词而是把规则列清楚然后搜索解空间的朴素思想。这道题的解法还有很多变体比如可以用位运算优化used数组也可以用舞蹈链处理更复杂的精确覆盖问题。但那是另一个深水区了。对大多数人来说掌握三重循环、理解全排列回溯、学会约束抽象这三步已经能把这类谁不和谁配对的题解得很漂亮。说回这道题本身。我每次带新人学Java都会让他们先动手推导答案再对比代码实现效果比直接敲代码好得多。这道题真正教会我们的不是记住某个循环套路而是学会把自然语言里的规则拆成程序能判断的条件再用一个可扩展的结构去承载它们。下次看到谁不能和谁在一起的题目你就能条件反射地想到列变量、定值域、写约束、枚举过滤按这个顺序做下去问题自然会解开。