美好的二月从WA一道简单题开始。
题目链接：https://leetcode-cn.com/problems/fair-candy-swap/
描述
爱丽丝和鲍勃有不同大小的糖果棒：
A[i]是爱丽丝拥有的第i根糖果棒的大小，B[j]是鲍勃拥有的第j根糖果棒的大小。因为他们是朋友，所以他们想交换一根糖果棒，这样交换后，他们都有相同的糖果总量。（一个人拥有的糖果总量是他们拥有的糖果棒大小的总和。）
返回一个整数数组
ans，其中ans[0]是爱丽丝必须交换的糖果棒的大小，ans[1]是 Bob 必须交换的糖果棒的大小。如果有多个答案，你可以返回其中任何一个。保证答案存在。
示例1
输入： A = [1,1], B = [2,2]
输出：[1,2]
示例2
输入： A = [1,2], B = [2,3]
输出：[1,2]
数据范围
1 <= A.length <= 100001 <= B.length <= 100001 <= A[i] <= 1000001 <= B[i] <= 100000- 保证爱丽丝与鲍勃的糖果总量不同。
- 答案肯定存在。
分析
希望满足交换后的总和相等，不难看出交换的数量需要满足一定的关系。
我们设Allice拿来交换的大小是changeA，Bob拿来交换的大小是changeB；两人交换前分别具有sumA和sumB总量的糖果，则两人交换之后拥有的总量分别是：
- Allice：
sumA - changeA + changeB - Bob：
sumB - changeB + changeA
两个式子是相等的，那么我们进行相减，得到sumA - sumB + 2changeB - 2changeA = 0；
进一步使用diff来表示sumA - sumB，即初始总量之差，则对等式变形能得到：changeA = changeB + diff / 2。
这就是我们最终使用的公式，changeA和changeB满足的关系。
暴力
我们可以循环Allice的每一个糖果棒，即对于每一个changeA，只需要使用公式计算changeB，然后判断changeB是否存在于Bob的集合中；当我们找到了一对changeA和changeB同时存在，就是最终的答案。
则转化成为一个搜索问题，对于一个特定的changeB，在Bob的集合中查找它是否存在。
使用顺序搜索，一层循环changeA，每个changeA还需要遍历一次Bob的集合，复杂度是O(n^2)，显然不行；
使用二分搜索，一层循环changeA，每个changeA搜索对应的changeB只需要花费logn，则总复杂度是O(nlogn)，可以一试。
第一次WA，二分写错了…
暴力二分，AC代码：
class Solution {
public:
typedef long long LL;
const int INF = 0xffffff;
int bSearch(int target, vector<int> v)
{
int left = 0;
int right = v.size() - 1;
int res = -INF;
while (left <= right)
{
int mid = (left + right) / 2;
if (v[mid] < target) // 答案在右半部分
{
left = mid + 1;
continue;
}
else if (v[mid] > target) // 答案在左半部分
{
right = mid - 1;
continue;
}
else
{
res = target;
break;
}
}
return res; // 没找到，-INF；找到，target
}
vector<int> fairCandySwap(vector<int>& A, vector<int>& B) {
sort(A.begin(), A.end());
sort(B.begin(), B.end());
LL sum_a = 0;
LL sum_b = 0;
for (int i = 0; i < A.size(); ++i)
sum_a += A[i];
for (int i = 0; i < B.size(); ++i)
sum_b += B[i];
LL diff = sum_a - sum_b;
int change_a, change_b;
// change_a = change_b + diff / 2
vector<int> res;
for (int i = 0; i < A.size(); ++i)
{
change_a = A[i];
change_b = change_a - diff / 2;
// cout << change_a << " " << change_b << endl;
if(bSearch(change_b, B) != -INF) // 找到
{
res.push_back(change_a);
res.push_back(change_b);
break;
}
}
return res;
}
};
对于一个
vector进行二分查找，初始化right = v.size() - 1，第一次WA的时候没有减一；while循环，判断条件应该是
left <= right，第一次WA的时候也没有等号。二分还是细啊o(╥﹏╥)o
不过表现就烂成蛇皮了。
双指针
在查找changeA和changeB的时候是否存在O(n) 的办法呢？是存在的。
假设Allice和Bob的集合都已经从小到大排好序，使用一个pA指向Allice的集合起始元素，pB指向Bob的集合起始元素，用如下规则进行移动：
- 当
*pA > *pB + diff / 2的时候，pB++； - 当
*pA < *pB + diff / 2的时候，pA++； - 两者相等的时候，就是我们要的答案。
此法的正确性主要来自于集合的有序性。第一种情况出现时，说明pB指向的元素太小了，changeB需要再大一点，故将pB向后移动；当第二种情况出现的时候，说明pA指向的元素太小了，changeA需要再大一点。
二分和双指针法的最大复杂度其实都是O(nlogn)（排序），但是在查找过程中显然双指针更快一些。
AC代码：
class Solution {
public:
typedef long long LL;
vector<int> fairCandySwap(vector<int>& A, vector<int>& B) {
sort(A.begin(), A.end());
sort(B.begin(), B.end());
LL sum_a = 0;
LL sum_b = 0;
for (int i = 0; i < A.size(); ++i)
sum_a += A[i];
for (int i = 0; i < B.size(); ++i)
sum_b += B[i];
LL diff = sum_a - sum_b;
vector<int> res;
vector<int>::iterator pA = A.begin();
vector<int>::iterator pB = B.begin();
while (pA != A.end() && pB != B.end())
{
if (*pA > *pB + diff / 2) // pB指向的目标太小
{
pB++;
}
else if (*pA < *pB + diff / 2) // pA指向的目标太小
{
pA++;
}
else
{
res.push_back(*pA);
res.push_back(*pB);
break;
}
}
return res;
}
};
表现还不错。
官方题解中提到的哈希表，在最开始构思的时候就想到了，但是懒得再查STL的用法，故放弃。
题解中有个老哥与我的双指针方法一毛一样，但是我的做法是独立想出来的，故不将其放入参考资料中。
参考资料
[1] 力扣官方题解.公平的糖果交换[EB/OL].2021-02-01