3妹："去吗？配吗？这褴褛的披风。战吗？战啊！以最卑微的梦。致那黑夜中的呜咽与怒吼。谁说站在光里的才算英雄……"
3妹在慷慨激昂的唱着孤勇者。
2哥：3妹，没想到你们女生也喜欢《孤勇者》这首歌啊，我还以为只有男生喜欢呢， 只是为什么你唱的这么悲伤啊？
3妹：别提了，今天面试又被鄙视了，问的算法题做出来了，可是面试官说复杂太高了，呜呜😭。
2哥：问的什么题目啊，让我看一下？
题目
爱丽丝和鲍勃拥有不同总数量的糖果。给你两个数组 aliceSizes 和 bobSizes ，aliceSizes[i] 是爱丽丝拥有的第 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[i], 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[i];
}
int sum2 = 0;
for (int i = 0; i < bobSizes.length; i++) {
sum2 += bobSizes[i];
}
int[] res = new int[2];
for (int i = 0; i < aliceSizes.length; i++) {
for (int j = 0; j < bobSizes.length; j++) {
if (sum1 - aliceSizes[i]+bobSizes[j] == sum2 - bobSizes[j]+aliceSizes[i]) {
return new int[] {
aliceSizes[i], bobSizes[j]
};
}
}
}
return new int[]{-1,-1};
}
}
2哥：解法是没错的，可是这个解法的时间复杂度是o(n^2), 的确挺高的，你觉得有什么好的解法吗？
3妹：没有想到，郁闷啊。
思路：
2哥：你看这个if表达式：if (sum1 - aliceSizes[i]+bobSizes[j] == sum2 - bobSizes[j]+aliceSizes[i])
为true时， aliceSizes[i]， bobSizes[j] 可以等价为： aliceSizes[i] =( (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;
}
}
网友评论