各位题友大家好，今天是每日算法题公众号坚持日更的第 8 天。今天力扣上的每日一题是第 839 题「839. 相似字符串组」。可以通过每日一题的小程序查看题目详情：

题目大意

Alice 和 Bob 两个人手里拥有的糖果🍬分别用 A 和 B 表示， A[i] 和 B[i] 分别表示 Alice 和 Bob 两个人手中的糖果的大小。

因为他们是好朋友，所以就想通过交换一个糖果的方式，使得每个人拥有糖果的总大小相等。求两者需要交换的糖果大小，用 res = [a, b] 表示。其中 a 是 Alice 需要交换的糖果大小，b 是 Bob 需要交换的糖果的大小。

示例

输入：A = [1,2], B = [2,3]
输出：[1,2]
解释：Alice 拿出大小为 1 的糖果，与 Bob 拿出的大小为 2 的糖果进行交换。交换后，两者的糖果分别是 A = [2, 2], B = [1, 3]。糖果的大小之和都为 4.

数据范围

  • 1 <= A.length <= 10000
  • 1 <= B.length <= 10000

解题思路

今天的题目是个 Easy 题目，看了数据范围小于等于 10000， 就不要想太多了，可以直接上 O(N) 的解法！

当两个小朋友交换完了糖果🍬之后，两人手中的糖果大小总和就相等了。那这个数字是多少呢？很显然是两个小朋友目前手中糖果的平均数。

所以，我们可以先求出最终两者手中的糖果大小之和是多少，设为 target 。然后逐个判断 Alice 的糖果 A[i] ，计算如果把该糖果交换出去，Bob 应该给 Alice 多大的糖果呢？答案应该是 target - (Alice的糖果总和 - A[i]) ,即 Alice 期望的糖果大小之和 target，减去 Alice 剩余的糖果大小之和。

那么问题来了：如果 Alice 想要用 A[i] 跟 Bob 交换，那么 Bob 手里面有没有 Alice 此时想要的糖果大小呢？即 target - (Alice的糖果总和 - A[i]) 是否在数组 B 中？

由于遍历 Alice 的糖果需要 O(N) 时间复杂度，此时留给 Bob 查找手里是否有 Alice 想要的这个糖果的时间复杂度只剩 O(1) 了。因为如果也用 O(N) 的时间复杂度查找出来，那么总时间复杂度是 O(N ^ 2) ，数组长度是 10000， 导致总计算量到达 10 ^ 8 ，可能会超时。

在常用的数据结构中，只有 Set 能够满足在 O(1) 时间内，判断一个元素是否存在。我们使用 Set 在 Bob 手中查找是否包含目标糖果。

代码

本题的代码比较简单。

  1. 求数组 A、数组 B 所有糖果大小的总和；使用 set 保存 B 中的各个元素；
  2. 求出两个小朋友手中糖果大小总和相等时的目标 target；
  3. 遍历 A 中的每个糖果，求如果把该糖果交换出去，期望 Bob 交换的糖果大小 expect_b。
  4. 从 B 的 set 中查找是否包含 expect_b，如果包含则说明 [a, expect_b] 是一种可以满足要求的交换。

时间复杂度：O(N)，因为只对数组 A 遍历了一次。
空间复杂度：O(N)，因为用了 set 保存数组 B 的所有元素。

使用 Python2 写的代码如下。

  1. class Solution(object):
  2.     def fairCandySwap(self, A, B):
  3.         """
  4.         :type A: List[int]
  5.         :type B: List[int]
  6.         :rtype: List[int]
  7.         """
  8.         sum_A, sum_B, set_B = sum(A), sum(B), set(B)
  9.         target = (sum_A + sum_B) // 2
  10.         for a in A:
  11.             expect_b = target - (sum_A - a)
  12.             if expect_b in set_B:
  13.                 return [a, expect_b]
  14.         return []

刷题心得

今天这个题虽然简单，但还是有可以积累的新知识的：

  1. 时间复杂度的估计，要学会根据数据规模，判断应该用什么时间复杂度的算法。
  2. 根据时间复杂度寻找合适的算法/数据结构，因此需要牢记算法/数据结构的时间复杂度。
  3. set 是一种拿空间换时间的数据结构，能够在 O(1) 的时间内判断某个元素是否存在其中。

欢迎加入刷题群

目前已经近 2000 人加入了每日一题打卡群。加入方式是通过每日一题打卡网站。每天都会同步力扣每日一题，这是个互相帮助、互相监督的算法题打卡网站，其地址是 https://www.ojeveryday.com/
888. 公平的糖果棒交换 - 图1

想加入千人刷题群的朋友，可以复制上面的链接到浏览器，然后在左侧点击「加入组织」，提交力扣个人主页，即可进入刷题群。期待你早日加入。

也可点击 「阅读原文」，直接提交力扣个人主页。

关于作者

我是本文的作者是负雪明烛，毕业于北京邮电大学，目前就职于阿里巴巴。坚持刷算法题 5 年，共计刷了 800 多道算法题。做过的每个算法题都在 CSDN 上写题解博客，获得好评无数，CSDN 的累计阅读量已经 160万 次！博客地址是：https://blog.csdn.net/fuxuemingzhu
「每日算法题」公众号是我维护的一个算法题解公众号，主要讲解算法题的解法，也会分享找工作的经验。欢迎关注。
888. 公平的糖果棒交换 - 图2

题目来源：839. 相似字符串组https://leetcode-cn.com/problems/similar-string-groups/