原文链接: https://leetcode-cn.com/problems/sum-swap-lcci

英文原文

Given two arrays of integers, find a pair of values (one value from each array) that you can swap to give the two arrays the same sum.

Return an array, where the first element is the element in the first array that will be swapped, and the second element is another one in the second array. If there are more than one answers, return any one of them. If there is no answer, return an empty array.

Example:

Input: array1 = [4, 1, 2, 1, 1, 2], array2 = [3, 6, 3, 3]
Output: [1, 3]

Example:

Input: array1 = [1, 2, 3], array2 = [4, 5, 6]
Output: []

Note:

• 1 <= array1.length, array2.length <= 100000

中文题目

给定两个整数数组，请交换一对数值（每个数组中取一个数值），使得两个数组所有元素的和相等。

返回一个数组，第一个元素是第一个数组中要交换的元素，第二个元素是第二个数组中要交换的元素。若有多个答案，返回任意一个均可。若无满足条件的数值，返回空数组。

示例:

输入: array1 = [4, 1, 2, 1, 1, 2], array2 = [3, 6, 3, 3]
输出: [1, 3]

示例:

输入: array1 = [1, 2, 3], array2 = [4, 5, 6]
输出: []

提示：

• 1 <= array1.length, array2.length <= 100000

通过代码

高赞题解

解题思路

• 先求两个数组的差值diff = sum(a)-sum(b), 如果为奇数直接return [], 因为交换任何数得到的diff一定是两个数字差值的2倍
• 然后将数组b作为集合, 遍历数组a, 判断其每个元素-diff//2是否在b集合中, 在的话即为所求

代码

class Solution:
    def findSwapValues(self, array1: List[int],
                       array2: List[int]) -> List[int]:
        diff = sum(array1) - sum(array2)
        if diff & 1: return []
        diff >>= 1
        s2 = set(array2)
        for a in array1:
            if a - diff in s2:
                return [a, a - diff]
        return []

统计信息

通过次数	提交次数	AC比率
10072	21695	46.4%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言