文章目錄

• • 1. 題目
  • 2. 解題
  • • 2.1 暴力查找
    • 2.2 哈希set

1. 題目

愛麗絲和鮑勃有不同大小的糖果棒：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:vector<int> fairCandySwap(vector<int>& A, vector<int>& 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-i+j == s/2)return {i,j};return {};} };

2.2 哈希set

class Solution { public:vector<int> fairCandySwap(vector<int>& A, vector<int>& B) {int s1 = 0, s2 = 0, s;unordered_set<int> 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(n²) 快很多

總結

以上是生活随笔為你收集整理的LeetCode 888. 公平的糖果交换（哈希set）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。