刷爆力扣之公平的糖果交换

刷爆力扣之公平的糖果交换

HELLO，各位看官大大好，我是阿呆 🙈🙈🙈
今天阿呆继续记录下力扣刷题过程，收录在专栏算法中 😜😜😜

该专栏按照不同类别标签进行刷题，每个标签又分为 Easy、Medium、Hard 三个等级 👊👊👊

本部分所有题目均来自于LeetCode 网，并于每道题目下标明具体力扣网原题链接 🏃🏃🏃

OK，兄弟们，废话不多直接上题，冲冲冲 🌞🌞🌞

一 🏠 题目描述

888. 公平的糖果交换

爱丽丝和鲍勃拥有不同总数量的糖果。给你两个数组 aliceSizes 和 bobSizes ，aliceSizes[i] 是爱丽丝拥有的第 i 盒糖果中的糖果数量，bobSizes[j] 是鲍勃拥有的第 j 盒糖果中的糖果数量

两人想要互相交换一盒糖果，这样在交换之后，他们就可以拥有相同总数量的糖果。一个人拥有的糖果总数量是他们每盒糖果数量的总和

返回一个整数数组 answer，其中 answer[0] 是爱丽丝必须交换的糖果盒中的糖果的数目，answer[1] 是鲍勃必须交换的糖果盒中的糖果的数目。如果存在多个答案，你可以返回其中 任何一个 。题目测试用例保证存在与输入对应的答案

示例 1：

输入：aliceSizes = [1,1], bobSizes = [2,2]
输出：[1,2]
1
2

示例 2：

输入：aliceSizes = [1,2], bobSizes = [2,3]
输出：[1,2]
1
2

示例 3：

输入：aliceSizes = [2], bobSizes = [1,3]
输出：[2,3]
1
2

示例 4：

输入：aliceSizes = [1,2,5], bobSizes = [2,4]
输出：[5,4]
1
2

提示：

• 1 <= aliceSizes.length, bobSizes.length <= 104
• 1 <= aliceSizes[i], bobSizes[j] <= 105
• 爱丽丝和鲍勃的糖果总数量不同
• 题目数据保证对于给定的输入至少存在一个有效答案

二 🏠破题思路

2.1 🚀 关键信息

解决问题第一步，当然先提取题目字面上的关键信息 😎😎😎

互相交换一盒糖果，拥有相同总数量的糖果，即伪代码如下 🌺🌺🌺

sum1 = count(aliceSizes) , sum2 = count(bobSizes) //两人糖果总数量
sum1 - aliceSizes[x] + bobSizes[y] = sum2 - bobSizes[y] + aliceSizes[x] //交换后等式成立
1
2

提取完题目中的关键信息后，直接进入第二阶段，思路整理 😃😃😃

2.2 🚀 思路整理

哈希表法：把上述等式转换得 bobSizes[y] = ( sum2 - sum1 + 2 * aliceSizes[x] ) / 2 ，易知可使用哈希表法先将 bobSizes 中的数字存入哈希表， 提升查询效率（方法一） 🌷🌷🌷

双指针法：虽不及哈希表法，但还算巧妙，为开阔思维单列出

首先对 aliceSizes 和 bobSizes 进行排序，定义双指针 i ，j 和 target = (sum1 - sum2) / 2 ，双指针分别从已排序的 aliceSizes 和 bobSizes 左端开始移动 🐌🐌🐌

若 aliceSizes[i] - bobSizes[j] 小于 target ，说明 aliceSizes[i] 小了，++i

若 aliceSizes[i] - bobSizes[j] 大于 target ，说明 bobSizes[j] 小了，++j

若 aliceSizes[i] - bobSizes[j] 等于 target ，则说明等式成立，返回结果 🐳🐳🐳

整理完解题思路后，直接进入第三阶段，代码实现 😃😃😃

三 🏠 代码详解

3.1 🚀 代码实现

按照我们刚才的破题思路，直接代码走起来 👇👇👇👇

vector fairCandySwap(vector& aliceSizes, vector& bobSizes) { //哈希表法
    int sumA = accumulate(aliceSizes.begin(), aliceSizes.end(), 0); //求和糖果总数量
    int sumB = accumulate(bobSizes.begin(), bobSizes.end(), 0); //求和糖果总数量
    
    int delta = (sumA - sumB) / 2; //先计算出等式成立的定值
    unordered_set rec(aliceSizes.begin(), aliceSizes.end()); //将aliceSizes放入set

    for (auto& y : bobSizes) { //遍历 bobSizes
        int x = y + delta; //求出满足等式的 aliceSizes 元素值
        if (rec.count(x)) { //若存在于 aliceSizes 
            return{ x, y }; //返回结果
        }
    }
    return {}; //返回结果
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

按照我们刚才的破题思路，直接代码走起来 👇👇👇👇

vector fairCandySwap(vector& aliceSizes, vector& bobSizes) { //双指针法
    int sum1 = accumulate(aliceSizes.cbegin(), aliceSizes.cend(), 0); //求和糖果总数量
    int sum2 = accumulate(bobSizes.cbegin(), bobSizes.cend(), 0); //求和糖果总数量
    
    std::sort(aliceSizes.begin(), aliceSizes.end()); //排序
    std::sort(bobSizes.begin(), bobSizes.end()); //排序

    int target = (sum1 - sum2) / 2; //计算出等式成立的定值
    int i = 0, j = 0; //定义双指针
    int len1 = aliceSizes.size(), len2 = bobSizes.size(); //获取数组长度
    while (i != len1 && j != len2) { //均从左端开始遍历
        int curr = aliceSizes[i] - bobSizes[j]; //计算当前值与等式成立定值比较

        if (curr == target) return{ aliceSizes[i], bobSizes[j] }; //返回结果
        else if (curr > target) ++j; //说明 bobSizes[j] 小了
        else ++i; //说明 aliceSizes[i] 小了
    }

    return{}; //返回结果
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

3.2 🚀 细节解析

看完 👀👀👀 全注释版的代码实现后，相信看官大大对整体逻辑已经是大写的 OK 了 😃😃😃

那么我们挖掘上述实现的晦涩细节 😖😖😖 进行解析，直接开干，走起来 👇👇👇👇

unordered_set rec(aliceSizes.begin(), aliceSizes.end()); //将aliceSizes放入set
1

这里与常规哈希表法不同之处在于，该题不需要对数组各元素计数，而只关心 aliceSizes 值。与哈希表相比，它和数组间转换逻辑更简洁，且 count 方法同样好用 🌼🌼🌼

四 🏠 心路历程

为方便各位看官大大了解博主真实刷题过程，我把当时状态纯纯真实还原，记录在心路历程这一小节，不感兴趣的小伙伴可以直接跳过哈

博主在第一阶段提取 🚀 关键信息并没有问题，在第二阶段 🚀 思路整理中联想到使用哈希表法，未联想到双指针法。但对于实现哈希表法的想法层面，挨个置入哈希表感觉太呆了（未联想到使用 set 解决该问题 😭😭😭）

所以博主的这道题也是在阅读完官方解析后，解出来并加以记录的

五 🏠 结语

身处于这个浮躁的社会，却有耐心看到这里，你一定是个很厉害的人吧 👍👍👍

如果各位看官大大觉得文章有帮助的话，别忘了点赞 + 关注哦，你们的鼓励就是我最大的动力

博主还会不断更新更优质的内容，加油吧！技术人！ 💪💪💪