算法题 公平的糖果交换

公平的糖果交换

问题描述

爱丽丝和鲍勃有不同大小的糖果：aliceSizes[i]是爱丽丝拥有的第i盒糖果的大小，bobSizes[j]是鲍勃拥有的第j盒糖果的大小。

因为他们非常友好，所以希望交换一盒糖果，使得交换后两人拥有的糖果总量相等。

返回一个整数数组answer，其中answer[0]是爱丽丝交换的糖果棒大小，answer[1]是鲍勃交换的糖果棒大小。

约定：

• 保证答案存在
• 答案唯一（除了顺序可能不同）

示例：

输入:aliceSizes=[1,1],bobSizes=[2,2]输出:[1,2]解释:爱丽丝总和=2，鲍勃总和=4，交换后都是3输入:aliceSizes=[1,2],bobSizes=[2,3]输出:[1,2]输入:aliceSizes=[2],bobSizes=[1,3]输出:[2,3]

算法思路

1. 数学：

   • 爱丽丝总和为sumA，鲍勃总和为sumB
   • 交换糖果a（爱丽丝）和b（鲍勃）后：
     • 爱丽丝新总和：sumA - a + b
     • 鲍勃新总和：sumB - b + a
   • 要求相等：sumA - a + b = sumB - b + a
   • 化简得：2b = sumB - sumA + 2a
   • 进一步：b = a + (sumB - sumA) / 2

2. 关键：

   • diff = (sumB - sumA) / 2
   • 对于爱丽丝的每个糖果a，需要找到鲍勃的糖果b = a + diff
   • 这样交换后两人总和相等

代码实现

方法一：哈希表查找

importjava.util.*;classSolution{/** * 公平的糖果交换 * * @param aliceSizes 爱丽丝的糖果数组 * @param bobSizes 鲍勃的糖果数组 * @return 交换的糖果对 [alice_candy, bob_candy] * * 算法思路： * 1. 计算两人糖果总和 * 2. 计算需要的差值 diff = (sumB - sumA) / 2 * 3. 对于爱丽丝的每个糖果 a，查找鲍勃是否有糖果 b = a + diff */publicint[]fairCandySwap(int[]aliceSizes,int[]bobSizes){// 计算爱丽丝和鲍勃的糖果总和intsumA=0,sumB=0;for(intcandy:aliceSizes){sumA+=candy;}for(intcandy:bobSizes){sumB+=candy;}// 计算差值：b = a + (sumB - sumA) / 2intdiff=(sumB-sumA)/2;// 将鲍勃的糖果放入哈希集合，快速查找Set<Integer>bobSet=newHashSet<>();for(intcandy:bobSizes){bobSet.add(candy);}// 遍历爱丽丝的每个糖果，查找对应的鲍勃糖果for(inta:aliceSizes){intb=a+diff;if(bobSet.contains(b)){returnnewint[]{a,b};}}returnnewint[]{};}}

方法二：使用Stream

classSolution{/** * 使用Java 8 Stream */publicint[]fairCandySwap(int[]aliceSizes,int[]bobSizes){intsumA=Arrays.stream(aliceSizes).sum();intsumB=Arrays.stream(bobSizes).sum();intdiff=(sumB-sumA)/2;Set<Integer>bobSet=Arrays.stream(bobSizes).boxed().collect(Collectors.toSet());returnArrays.stream(aliceSizes).filter(a->bobSet.contains(a+diff)).mapToObj(a->newint[]{a,a+diff}).findFirst().orElse(newint[]{});}}

算法分析

• 时间复杂度：O(m + n)

  • m = aliceSizes.length, n = bobSizes.length
  • 计算总和：O(m + n)
  • 构建哈希集合：O(n)
  • 查找过程：O(m)
  • 总体：O(m + n)

• 空间复杂度：O(min(m, n))

  • 哈希集合存储较小数组的所有元素

算法过程

1：aliceSizes = [1,1], bobSizes = [2,2]

计算过程：

sumA = 1 + 1 = 2 sumB = 2 + 2 = 4 diff = (4 - 2) / 2 = 1 鲍勃的集合: {2, 2} → {2} (HashSet自动去重) 遍历爱丽丝的糖果: - a = 1: b = 1 + 1 = 2, 2 ∈ {2} - 返回 [1, 2]

2：aliceSizes = [1,2], bobSizes = [2,3]

计算过程：

sumA = 1 + 2 = 3 sumB = 2 + 3 = 5 diff = (5 - 3) / 2 = 1 鲍勃的集合: {2, 3} 遍历爱丽丝的糖果: - a = 1: b = 1 + 1 = 2, 2 ∈ {2,3} - 返回 [1, 2]

3：aliceSizes = [2], bobSizes = [1,3]

计算过程：

sumA = 2 sumB = 1 + 3 = 4 diff = (4 - 2) / 2 = 1 鲍勃的集合: {1, 3} 遍历爱丽丝的糖果: - a = 2: b = 2 + 1 = 3, 3 ∈ {1,3} - 返回 [2, 3]

测试用例

importjava.util.*;publicclassTest{publicstaticvoidmain(String[]args){Solutionsolution=newSolution();// 测试用例1：标准示例int[]alice1={1,1};int[]bob1={2,2};int[]result1=solution.fairCandySwap(alice1,bob1);System.out.println("Test 1: "+Arrays.toString(result1));// [1,2]// 测试用例2：不同大小int[]alice2={1,2};int[]bob2={2,3};int[]result2=solution.fairCandySwap(alice2,bob2);System.out.println("Test 2: "+Arrays.toString(result2));// [1,2]// 测试用例3：单元素int[]alice3={2};int[]bob3={1,3};int[]result3=solution.fairCandySwap(alice3,bob3);System.out.println("Test 3: "+Arrays.toString(result3));// [2,3]// 测试用例4：大数值int[]alice4={1,2,5};int[]bob4={2,4};int[]result4=solution.fairCandySwap(alice4,bob4);System.out.println("Test 4: "+Arrays.toString(result4));// [5,4]// 测试用例5：负数int[]alice5={-1,2};int[]bob5={1,0};int[]result5=solution.fairCandySwap(alice5,bob5);System.out.println("Test 5: "+Arrays.toString(result5));// [-1,0]// 测试用例6：大量重复元素int[]alice6={1,1,1,1,1};int[]bob6={2,2,2,2,2,2,2};int[]result6=solution.fairCandySwap(alice6,bob6);System.out.println("Test 6: "+Arrays.toString(result6));// [1,2]// 测试用例7：大数组int[]alice7=newint[10000];int[]bob7=newint[10000];Arrays.fill(alice7,1);Arrays.fill(bob7,3);int[]result7=solution.fairCandySwap(alice7,bob7);System.out.println("Test 7: "+Arrays.toString(result7));// [1,3]}}

关键点

1. 数学：

   • 将问题转化为简单的数学等式
   • 避免暴力枚举所有可能的交换组合

2. 哈希表：

   • 将查找时间从 O(n) 优化到 O(1)
   • 总体时间复杂度从 O(m×n) 优化到 O(m+n)

常见问题

1. 为什么(sumB - sumA)一定是偶数？
   • 交换后总和相等，所以sumA - a + b = sumB - b + a
   • 整理得sumB - sumA = 2(b - a)，右边是偶数