華為面試題：交換數組元素使兩數組和的差值最小化

華為面試題：交換數組元素使兩數組和的差值最小化

在瀏覽技術論壇時，偶然發現一道被稱為「華為面試題（8分鐘寫出代碼）」的經典算法問題。雖然真實性無從考證，但題目本身極具啟發性，值得深入探討。

問題描述

給定兩個大小均為 n 的數組 a 和 b。允許交換兩數組中對應位置的元素（即交換 a[i] 和 b[i]），目標是使 sum(a) - sum(b) 的絕對值最小。

核心思路

許多前輩的解法引入了排序，但實際上排序並非必要。因為 sum(a) - sum(b) 的值僅取決於元素值的集合，與順序無關。我們可以定義差值數組 c[i] = a[i] - b[i]，則原始差值 sum = Σc[i]。若交換第 i 位元素，新差值 sum_new = sum - 2*c[i]。因此，問題轉化為：選擇一個索引 i，使 |sum - 2*c[i]| 最小。

算法實現

int sum = 0;
int c[n];
for (int i = 0; i < n; i++) {
    c[i] = a[i] - b[i];
    sum += c[i];
}
for (int i = 0; i < n; i++) {
    int sum_new = sum - 2 * c[i];
    if (sum_new * sum_new < sum * sum) { // 絕對值變小，說明交換有效
        // 使用 XOR 交換 a[i] 和 b[i]
        a[i] ^= b[i];
        b[i] ^= a[i];
        a[i] ^= b[i];
        sum = sum_new; // 更新當前最小差值
    }
}

關鍵點解析

• 無需排序：直接遍歷差值數組即可找到最優交換位置，時間複雜度 O(n)，空間複雜度 O(n)。
• XOR 交換技巧：無需臨時變量即可交換兩整數值，展示位運算功力。
• 絕對值比較：通過比較平方值避免 abs() 函數調用，提升性能。

擴展思考

若允許任意次數交換（不限於對應位置），問題將演變為經典的「分割數組使和最接近」的背包問題，需動態規劃求解。但本題限制條件明確，貪心策略即可得最優解。