888. 公平的糖果交换

题目描述：

爱丽丝和鲍勃拥有不同总数量的糖果。给你两个数组 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⁴
• 1 <= aliceSizes[i], bobSizes[j] <= 10⁵
• 爱丽丝和鲍勃的糖果总数量不同。
• 题目数据保证对于给定的输入至少存在一个有效答案。

---

解题分析及思路：

方法：模拟

思路：

从 aliceSizes 中挑选一个糖果 x ，从 bobSizes 中挑选一个糖果 y ，使得 aliceSizes 将 x 和 bobSizes 中的 y 交换，最终 aliceSizes 和 bobSizes 的和相等。

即：Sum_aliceSizes - x + y = Sum_bobSizes + x - y ，得 x - y = (Sum_aliceSizes - Sum_bobSizes) / 2

所以在 aliceSizes 的某个数与 bobSizes 的某个数的差值等于 (Sum_aliceSizes - Sum_bobSizes) / 2 ，那么这两个数为结果。

• 首先将 aliceSizes 和 bobSizes 进行排序。
• 遍历两个数组，计算遍历时两个数的差值是否符合预期值
• 不符合时，分别移动两个数组的下标，使得最后能够找到结果

func fairCandySwap(aliceSizes []int, bobSizes []int) []int {
	sort.Ints(aliceSizes)
	sort.Ints(bobSizes)
	sum := 0
	for i := 0; i < len(aliceSizes); i++ {
		sum += aliceSizes[i]
	}
	for i := 0; i < len(bobSizes); i++ {
		sum -= bobSizes[i]
	}
	sub := sum / 2
	for i, j := 0, 0; i < len(aliceSizes) && j < len(bobSizes); {
		temp := aliceSizes[i] - bobSizes[j]
		if temp == sub {
			return []int{aliceSizes[i], bobSizes[j]}
		} else if temp > sub {
			j++
		} else {
			i++
		}
	}
	return []int{aliceSizes[len(aliceSizes)-1], bobSizes[len(bobSizes)-1]}
}`

复杂度：

• 时间复杂度：O(logN)
• 空间复杂度：O(1)

执行结果：

• 内存消耗:6.65 MB,击败了100.00% 的Go用户