交换对使总和相等

Question

问题：给定两个大小为 N 和 M 的整数数组 A[] 和 B[]，任务是检查是否存在一对值（每个数组中的一个值），以便交换pair 将使两个数组的总和相等。

我的做法：

求两个数组的总和。
找出总和较大的数组（用A[]表示）。
排序 A.
对于 B 中的所有值，在 A 中二分查找 (sum(A)-sum(B)/2 + B[i])，如果找到 return true.
Return 错误。

代码：

int sum(int a[], int n){
    int s=0;
    for(int i=0; i<n; i++){
        s+= a[i];
    }
    return s;
}

int findSwapValues(int A[], int n, int B[], int m)
{
    // Your code goes here
    int a = sum(A, n);
    int b = sum(B,m);
    int t;
    int *temp;
    
    if(a<b){
        temp  = A; 
        A = B;
        B = temp;
        t  = n;
        n = m;
        m = t;
        
        t = a;
        a = b;
        b = t;
    }
    
    sort(A, A+n);
    for(int i=0; i<m; i++){
        if(binary_search(A,A+n,(a-b)/2+B[i])){
            return 1;
        }
    }
    return -1;
}

疑问：我的算法在某些测试用例（不是 TLE）上失败了。由于测试用例非常大，很难推理出算法中的问题。我在网上搜索并了解其他方法。我唯一的好奇是为什么它不正确？

Answer 1

我认为您的代码中的错误是您发现 B[i] + (a-b)/2.

问题在于，如果 (a-b) 是奇数，除以 2 会将其四舍五入为最接近的整数，您最终会找到错误的值。

你可以做的是在交换数组之前检查差异是否为奇数，如果为真，直接 return -1 因为如果差异为奇数，则不这样的一对可以永远存在。

我希望我消除了你的疑虑:)。

交换对使总和相等

swap pair to make sum equal

arrays

sorting

algorithm

binary-search