【LeetCode】面试题 16.21. 交换和
质量还不错的一道题，适合用于考察二分法。
1. 题目
2. 分析
- 求出两个数组的总和，我们令总和少的为less，总和多的为more；
- 如果两个数组的总和是奇数，那么怎么都配不平，直接返回false；
- 如果两个数组的总和是偶数，那么可能配平。
- 先找出增量deta，即存在less + deta = more - deta
- 那么遍历总和小的数组，从中逐个判断数num，看是否在more那个数组中存在 num+deta 这个数，如果存在，即满足结果；如果最后没有找到，那么返回空集。
3. 代码
class Solution:def findSwapValues(self, array1: List[int], array2: List[int]) -> List[int]:# 二分法找出合适的增量 detatotal1 = total2 = 0for i in array1:total1 += ifor i in array2:total2 += iif (total1+total2) %2 == 1:return []# 找到较小值，较大值 deta = abs(total1 - total2)//2array1.sort()array2.sort()if total1 > total2:deta = -1 * deta# print(deta)# 以array1 为base，加减detafor i in range(len(array1)):num1 = array1[i]target = num1 + deta #判断目标数是否在array2中left = 0right = len(array2)-1while(left <= right):mid = (left+right)//2if array2[mid] < target:left = mid + 1elif array2[mid] >= target:right = mid -1if left!=len(array2) and array2[left] == target:return [num1, target]return []