凡客诚品售后,象山seo的优化,信托公司网站建设,石家庄市环保局网站建设项目备案系统文章目录1. 题目2. 解题2.1 暴力查找2.2 哈希set1. 题目
爱丽丝和鲍勃有不同大小的糖果棒#xff1a;A[i] 是爱丽丝拥有的第 i 块糖的大小#xff0c;B[j] 是鲍勃拥有的第 j 块糖的大小。
因为他们是朋友#xff0c;所以他们想交换一个糖果棒#xff0c;这样交换后#…
文章目录1. 题目2. 解题2.1 暴力查找2.2 哈希set1. 题目
爱丽丝和鲍勃有不同大小的糖果棒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]示例 3
输入A [2], B [1,3]
输出[2,3]示例 4
输入A [1,2,5], B [2,4]
输出[5,4]提示
1 A.length 10000
1 B.length 10000
1 A[i] 100000
1 B[i] 100000
保证爱丽丝与鲍勃的糖果总量不同。
答案肯定存在。来源力扣LeetCode 链接https://leetcode-cn.com/problems/fair-candy-swap 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 解题
2.1 暴力查找
class Solution {
public:vectorint fairCandySwap(vectorint A, vectorint B) {int s1 0, s2 0, s;for(int i : A)s1 i;for(int i : B)s2 i;s s1 s2;for(int i : A)for(int j : B)if(s1-ij s/2)return {i,j};return {};}
};2.2 哈希set
class Solution {
public:vectorint fairCandySwap(vectorint A, vectorint B) {int s1 0, s2 0, s;unordered_setint set;for(int i : A)s1 i;for(int i : B){s2 i;set.insert(i);}s s1 s2;for(int i : A)if(set.count(s/2 - s1 i))return {i,s/2 - s1 i};return {};}
};哈希可以实现 O(1) 的查找比暴力法 O(n2) 快很多
