教3妹学编程： 888. 公平的糖果互换

手机软件开发 · 2024-9-19 17:55:41

3妹："去吗？配吗？这褴褛的披风。战吗？战啊！以最卑微的梦。致那黑夜中的呜咽与咆哮。谁说站在光里的才算豪杰……"
3妹在慷慨鼓动的唱着孤勇者。
2哥：3妹，没想到你们女生也喜好《孤勇者》这首歌啊，我还以为只有男生喜好呢，只是为什么你唱的这么伤心啊？
3妹：别提了，本日口试又被藐视了，问的算法题做出来了，但是口试官说复杂太高了，呜呜?。
2哥：问的什么标题啊，让我看一下？
标题

爱丽丝和鲍勃拥有差别总数量的糖果。给你两个数组 aliceSizes 和 bobSizes ，aliceSizes 是爱丽丝拥有的第 i 盒糖果中的糖果数量，bobSizes[j] 是鲍勃拥有的第 j 盒糖果中的糖果数量。
两人想要相互互换一盒糖果，如许在互换之后，他们就可以拥有雷同总数量的糖果。一个人拥有的糖果总数量是他们每盒糖果数量的总和。
返回一个整数数组 answer，此中 answer[0] 是爱丽丝必须互换的糖果盒中的糖果的数量，answer[1] 是鲍勃必须互换的糖果盒中的糖果的数量。假如存在多个答案，你可以返回此中任何一个。标题测试用例包管存在与输入对应的答案。
示例 1：
输入：aliceSizes = [1,1], bobSizes = [2,2]
输出：[1,2]
示例 2：
输入：aliceSizes = [1,2], bobSizes = [2,3]
输出：[1,2]
示例 3：
输入：aliceSizes = [2], bobSizes = [1,3]
输出：[2,3]
示例 4：
输入：aliceSizes = [1,2,5], bobSizes = [2,4]
输出：[5,4]
提示：
1 <= aliceSizes.length, bobSizes.length <= 10^4
1 <= aliceSizes, bobSizes[j] <= 10^5
爱丽丝和鲍勃的糖果总数量差别。
标题数据包管对于给定的输入至少存在一个有效答案。
2哥：你是怎么做的呢？
3妹：就是双层for循环，找出互换的两个数总和相称就可以了。
方法一：

class Solution { public int[] fairCandySwap(int[] aliceSizes, int[] bobSizes) { int sum1 = 0; for (int i = 0; i < aliceSizes.length; i++) { sum1 += aliceSizes; } int sum2 = 0; for (int i = 0; i < bobSizes.length; i++) { sum2 += bobSizes; } int[] res = new int[2]; for (int i = 0; i < aliceSizes.length; i++) { for (int j = 0; j < bobSizes.length; j++) { if (sum1 - aliceSizes+bobSizes[j] == sum2 - bobSizes[j]+aliceSizes) { return new int[] { aliceSizes, bobSizes[j] }; } } } return new int[]{-1,-1}; }}2哥：解法是没错的，但是这个解法的时间复杂度是o(n^2), 简直挺高的，你以为有什么好的解法吗？
3妹：没有想到，忧郁啊。
思绪：

2哥：你看这个if表达式：if (sum1 - aliceSizes+bobSizes[j] == sum2 - bobSizes[j]+aliceSizes)
为true时， aliceSizes， bobSizes[j] 可以等价为： aliceSizes =( (sum1-sum2)/2) + bobSizes[j], 以是只要遍历bobSizes，只要找到( (sum1-sum2)/2) + bobSizes[j] 的值在aliceSizes 中就可以了。
3妹：哦，这么奥妙，我怎么当时就没想到呢，我按照如许写一下。
方法二 java代码：

class Solution { public int[] fairCandySwap(int[] aliceSizes, int[] bobSizes) { int sumA = Arrays.stream(aliceSizes).sum(); int sumB = Arrays.stream(bobSizes).sum(); int delta = (sumA - sumB) / 2; Set<Integer> rec = new HashSet<Integer>(); for (int num : aliceSizes) { rec.add(num); } int[] ans = new int[2]; for (int y : bobSizes) { int x = y + delta; if (rec.contains(x)) { ans[0] = x; ans[1] = y; break; } } return ans; }}

教3妹学编程： 888. 公平的糖果互换

所属分类: 问答交流

新帖推荐: 30日

推荐作品