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; }} |