LeetCode 解題筆記：2333. Minimum Sum of Squared Difference

作者：王一哲
日期：2026年10月10日


LeetCode 題目連結：2333. Minimum Sum of Squared Difference

解題想法

中等難度題，但是這題原來的通過率大約只有 22%，相當難。題目給兩個長度皆為 $n$ 的正整數陣列 $nums1, nums2$，可以對 $nums1$ 最多操作 $k1$ 次，對 $nums2$ 最多操作 $k2$ 次，每次操作可以將其中一個元素加 1 或減 1，要找出 $(nums1[i] - nums2[i])**2$ 加總的最小值。

這題在討論區主要有兩種寫法，分別是用最大優先佇列 (priority queue) 及桶子排序 (bucket sort)。我一開始有試著用最大優先佇列解題，將元素差距絕對值最小的組合數量放在佇列最上面，但是我可能沒有寫好，最多只能跑到第30筆測資就超時了。後來改用桶子排序順利過關，而且時間排名都還不錯。主要分成以下 3 個步驟：

1. 桶子排序，索引值為差距絕對值，內容為數量。桶子 $bucket$ 的長度開成測資陣列值上限加 1 的 $100001$，預設值為 $0$。用一個變數 $imax$ 記錄差距絕對值最大值。用一個 for 迴圈掃過所有元素，更新 $bucket$ 之中的數量及 $imax$。
2. 最多可以縮小差距 k1 + k2 次，從差距絕對值最大者開始縮小。
3. 用一個 for 迴圈跑 $i = 0$ 到 $i = imax$，答案 $ans$ 為 $i * i * bucket[i]$ 的加總，量值可以用 long long 儲存。

Python 程式碼

Runtime: 153 ms, beats 58.75%. Memory: 33.72 MB, beats 83.75%.

class Solution:
    def minSumSquareDiff(self, nums1: list[int], nums2: list[int], k1: int, k2: int) -> int:
        # 1. 桶子排序，索引值為差距絕對值，內容為數量
        imax = 0  # 差距絕對值最大值
        bucket = [0] * 100001
        for a, b in zip(nums1, nums2):
            diff = abs(a - b)
            imax = max(imax, diff)
            bucket[diff] += 1
        
        # 2. 最多可以縮小差距 k1 + k2 次，從差距絕對值最大者開始縮小
        rem = k1 + k2  # 剩下的操作次數
        for i in range(imax, 0, -1):
            val = bucket[i]
            if val == 0: continue  # 跳過數量為 0 的項目
            if rem >= val:  # 可操作次數大於等於 val
                bucket[i-1] += val  # 差距絕對值 i-1 對應的數量加 val
                bucket[i] = 0  # 差距絕對值 i 對應的數量歸零
                rem -= val  # 可操作次數減 val  
            else:  # 可操作次數小於 val
                bucket[i-1] += rem  # 差距絕對值 i-1 對應的數量加 rem
                bucket[i] -= rem  # 差距絕對值 i 對應的數量減 rem
                rem = 0  # 可操作次數歸零
            if rem == 0: break  # 無法再操作，中止迴圈
                
        # 3. 計算並回傳答案
        return sum(i * i * bucket[i] for i in range(imax + 1))

C++ 程式碼

Runtime: 4 ms, beats 97.21%. Memory: 119.19MB, beats 93.85%.

class Solution {
public:
    long long minSumSquareDiff(vector<int>& nums1, vector<int>& nums2, int k1, int k2) {
        /* 1. 桶子排序，索引值為差距絕對值，內容為數量 */
        int bucket[100001] = {0}, n = (int)nums1.size(), imax = 0;  // 桶子，長度，差距絕對值最大值
        for(int i = 0; i < n; i++) {
            int diff = abs(nums1[i] - nums2[i]);
            imax = max(imax, diff);
            bucket[diff]++;
        }
        
        /* 2. 最多可以縮小差距 k1 + k2 次，從差距絕對值最大者開始縮小 */
        int rem = k1 + k2;  // 剩下的操作次數
        for(int i = imax; i > 0; i--) {
            int val = bucket[i];
            if (val == 0) continue;  // 跳過數量為 0 的項目
            if (rem >= val) {  // 可操作次數大於等於 val
                bucket[i-1] += val;  // 差距絕對值 i-1 對應的數量加 val
                bucket[i] = 0;  // 差距絕對值 i 對應的數量歸零
                rem -= val;  // 可操作次數減 val  
            } else {  // 可操作次數小於 val
                bucket[i-1] += rem;  // 差距絕對值 i-1 對應的數量加 rem
                bucket[i] -= rem;  // 差距絕對值 i 對應的數量減 rem
                rem = 0;  // 可操作次數歸零
            }
            if (rem == 0) break;  // 無法再操作，中止迴圈
        }

        /* 3. 計算並回傳答案 */
        long long ans = 0LL;
        for(int i = 0; i <= imax; i++) {
            ans += (long long)i * (long long)i * (long long)bucket[i];
        }
        return ans;
    }
};

C 語言程式碼

Runtime: 4 ms, beats 100.00%. Memory: 17.23 MB, beats 100.00%.

#define max(a, b) ((a) > (b) ? (a) : (b))

long long minSumSquareDiff(int* nums1, int nums1Size, int* nums2, int nums2Size, int k1, int k2) {
    /* 1. 桶子排序，索引值為差距絕對值，內容為數量 */
    int bucket[100001] = {0}, imax = 0;  // 桶子，差距絕對值最大值
    for(int i = 0; i < nums1Size; i++) {
        int diff = abs(nums1[i] - nums2[i]);
        imax = max(imax, diff);
        bucket[diff]++;
    }
    
    /* 2. 最多可以縮小差距 k1 + k2 次，從差距絕對值最大者開始縮小 */
    int rem = k1 + k2;  // 剩下的操作次數
    for(int i = imax; i > 0; i--) {
        int val = bucket[i];
        if (val == 0) continue;  // 跳過數量 0 的項目
        if (rem >= val) {  // 可操作次數大於等於 val
            bucket[i-1] += val;  // 差距絕對值 i-1 對應的數量加 val
            bucket[i] = 0;  // 差距絕對值 i 對應的數量歸零
            rem -= val;  // 可操作次數減 val  
        } else {  // 可操作次數小於 val
            bucket[i-1] += rem;  // 差距絕對值 i-1 對應的數量加 rem
            bucket[i] -= rem;  // 差距絕對值 i 對應的數量減 rem
            rem = 0;  // 可操作次數歸零
        }
        if (rem == 0) break;  // 無法再操作，中止迴圈
    }

    /* 3. 計算並回傳答案 */
    long long ans = 0LL;
    for(int i = 0; i <= imax; i++) {
        ans += (long long)i * (long long)i * (long long)bucket[i];
    }
    return ans;
}