1674. Minimum Moves to Make Array Complementary

題目 / Problem

中文： 給定一個長度為偶數 n 的整數陣列 nums 與一個整數 limit。每次操作可以把 nums 中任一元素改成 [1, limit] 範圍內的任意整數。若對所有 i，nums[i] + nums[n-1-i] 都等於同一個數，則稱 nums 為「互補陣列」。請回傳使 nums 變成互補陣列所需的最少操作次數。

English: You are given an integer array nums of even length n and an integer limit. In one move, you may replace any element of nums with any integer in [1, limit]. The array is complementary if nums[i] + nums[n-1-i] is the same value for every index i. Return the minimum number of moves needed to make nums complementary.

Constraints / 限制 - 2 ≤ n ≤ 10^5, n is even. - 1 ≤ nums[i] ≤ limit ≤ 10^5.

Example / 範例

Input:  nums = [1,2,4,3], limit = 4
Output: 1
Explanation: change nums[2] from 4 → 2, getting [1,2,2,3]; every pair sums to 4.

名詞解釋 / Glossary

• 對稱配對 / Symmetric pair：陣列中的位置 i 與 n-1-i 配成一組；長度為 n 的陣列共有 n/2 組。Each index i is paired with n-1-i; an array of length n has n/2 such pairs.
• 目標總和 x / Target sum x：我們希望讓「每組對稱配對」的和都等於同一個 x。x 的合法範圍是 [2, 2*limit]（因為每個值都在 [1, limit]）。The value we want every pair to sum to; x lies in [2, 2*limit].
• 差分陣列 / Difference array：用 d[i] = a[i] - a[i-1] 表示原陣列的變化量，做「區間 +v」很快（只動兩個位置）；最後再做前綴和還原。An array storing changes between consecutive elements; lets you add v to a whole range in O(1) and recover the original via prefix sum.
• 前綴和 / Prefix sum：把陣列從頭累加起來，使得 pre[i] = a[0] + a[1] + ... + a[i]。Cumulative sum of an array.
• 配對的三種狀況 / Three cases per pair：對某個目標 x，一組配對 (a, b) 只會需要 0、1 或 2 次修改——0（原本就湊到 x）、1（改其中一個就夠）、2（兩個都得改）。For a fixed target x, a pair needs 0, 1, or 2 modifications.

思路

暴力解： 枚舉所有可能的目標 x ∈ [2, 2*limit]，對每個 x 掃過 n/2 組配對計算總代價，取最小。複雜度 O(n · limit)，當 n 和 limit 都到 10^5 時是 10^{10}，會超時。

關鍵觀察： 對某一組配對 (a, b)，令 lo = min(a, b)、hi = max(a, b)。把目標 x 從小到大走一遍，所需的修改次數呈現一個非常規則的「梯形」： - x ∈ [2, lo]：兩個都太小，得改兩個 → 代價 2。 - x ∈ [lo+1, hi+limit]：只改其中一個（讓較大者保留、把較小者改成 x - hi，或反之）就行 → 代價 1。 - x = lo + hi：原本就剛好 → 代價 0（在 1 區間中扣 1）。 - x ∈ [hi+limit+1, 2*limit]：要把較大者變更大但超過 limit，所以得改兩個 → 代價 2。

對每個 x 把所有配對的代價加總，就得到 f(x)。直接累加是 O(n · limit)，但是這些「+2、-1、-1、+1、+1」的變化都是區間性的——這正是差分陣列的用武之地。對每組配對，我們只需要在 4 個位置打標記：在 lo+1 處減 1（從 2 掉到 1），在 lo+hi 處再減 1（掉到 0），在 lo+hi+1 處加 1（彈回 1），在 hi+limit+1 處加 1（彈回 2）。最後做一次前綴和，就能在 O(limit) 內知道每個 x 的總代價。整體複雜度從 O(n · limit) 降到 O(n + limit)。

The brute force enumerates every possible target sum x ∈ [2, 2*limit] and, for each, scans all n/2 pairs — that's O(n · limit), too slow for the given limits. The key insight is that, for a single pair (a, b) with lo = min(a, b) and hi = max(a, b), the cost as a function of x is a piecewise constant "tub": cost 2 on [2, lo], cost 1 on [lo+1, hi+limit] (you fix just one side because the other already fits), cost 0 exactly at x = lo + hi, then cost 2 again on [hi+limit+1, 2*limit]. Summing these "tubs" over all pairs is a classic range-update job, so we use a difference array: per pair, we apply four point updates — -1 at lo+1, -1 at lo+hi, +1 at lo+hi+1, +1 at hi+limit+1. After one prefix-sum pass, f(x) for every x is available, and we return the minimum. Starting the prefix accumulator at n (the worst case, where every pair costs 2) keeps the arithmetic simple. Total: O(n + limit) time and space.

逐步走查 / Walkthrough

Input: nums = [1, 2, 4, 3], limit = 4. So n = 4, valid range of x is [2, 8].

配對 / Pairs | pair | a | b | lo | hi | 1-move range [lo+1, hi+limit] | 0-move point lo+hi | |---|---|---|---|---|---|---| | 0 | 1 | 3 | 1 | 3 | [2, 7] | 4 | | 1 | 2 | 4 | 2 | 4 | [3, 8] | 6 |

對差分陣列 d 打標記 / Apply diff updates (size 2·limit + 2 = 10)

For pair 0 (1, 3): d[2] -= 1, d[8] += 1, d[4] -= 1, d[5] += 1. For pair 1 (2, 4): d[3] -= 1, d[9] += 1, d[6] -= 1, d[7] += 1.

Resulting d for indices 2..9: [-1, -1, -1, +1, -1, +1, +1, +1].

前綴和掃描 / Sweep prefix sum starting from cur = n = 4:

Minimum is 1, achieved at x = 4 (or x = 6). Answer: 1. ✓

Solution — C

// 演算法 / Algorithm: 對每個對稱配對 (a, b)，目標和 x 所需的修改次數對 x 是一個
// "梯形" 函數 (2 → 1 → 0 → 1 → 2)。用差分陣列累計所有配對的代價，做一次前綴和
// 即可在 O(n + limit) 內找出最小的 f(x)。
// For each pair, the cost-vs-x curve is a fixed shape; sum them with a diff array
// and prefix-scan to find min f(x) in O(n + limit).

#include <stdlib.h>  // 引入 calloc / free / for calloc and free

int minMoves(int* nums, int numsSize, int limit) {
    int n = numsSize;                              // n 是陣列長度 / array length
    int size = 2 * limit + 2;                       // d 的大小需涵蓋索引 2..2*limit+1 / size covers indices up to 2*limit+1
    int* d = (int*)calloc(size, sizeof(int));       // calloc 配置並清零記憶體 / calloc allocates zero-filled memory
    if (d == NULL) return 0;                        // 防禦性檢查 / defensive null check

    for (int i = 0; i < n / 2; i++) {               // 走訪每組對稱配對 / iterate over each symmetric pair
        int a = nums[i];                            // 左邊元素 / left element of the pair
        int b = nums[n - 1 - i];                    // 右邊元素 (鏡像位置) / right element (mirror index)
        int lo = a < b ? a : b;                     // 較小值 / smaller value
        int hi = a < b ? b : a;                     // 較大值 / larger value

        // 從 x = lo+1 開始，本配對的代價從 2 掉到 1 / at x = lo+1 the cost drops 2 → 1
        d[lo + 1] -= 1;
        // 從 x = hi+limit+1 開始，本配對的代價又彈回 2 / at x = hi+limit+1 the cost climbs back 1 → 2
        d[hi + limit + 1] += 1;
        // x = lo+hi 時剛好原本就湊到 x，代價再扣 1 變 0 / at x = lo+hi the cost drops 1 → 0
        d[lo + hi] -= 1;
        // x = lo+hi+1 時離開那個點，代價彈回 1 / at x = lo+hi+1 the cost climbs back 0 → 1
        d[lo + hi + 1] += 1;
    }

    int ans = n;        // 最壞情況：每對都需 2 次修改，共 n 次 / worst case: every pair costs 2, total = n
    int cur = n;        // cur 累積 f(x)；起點取 n 代表 "所有配對皆代價 2" 的基線 / running f(x), baseline = n
    for (int x = 2; x <= 2 * limit; x++) {          // 掃過所有合法目標 x / sweep all valid target sums
        cur += d[x];                                 // 套用差分增量 = 前綴和 / apply diff = take prefix sum
        if (cur < ans) ans = cur;                    // 更新最小值 / track minimum
    }

    free(d);            // 釋放動態記憶體，避免洩漏 / free heap memory to avoid leaks
    return ans;         // 回傳最少修改次數 / return minimum number of moves
}

Solution — C++

// 演算法 / Algorithm: 同 C 版——以差分陣列在 O(n + limit) 內聚合每個配對的成本曲線，
// 再用前綴和找出讓總修改數最小的目標和 x。
// Same as C: aggregate per-pair cost curves into a diff array, prefix-sum, take the min.

#include <vector>      // STL 動態陣列 vector / dynamic array
#include <algorithm>   // 提供 std::min / for std::min
using namespace std;   // 省略 std:: 前綴 (僅在競賽/教學中使用) / drop the std:: prefix

class Solution {
public:
    int minMoves(vector<int>& nums, int limit) {
        int n = static_cast<int>(nums.size());     // 取得陣列長度 / get array length
        vector<int> d(2 * limit + 2, 0);            // 差分陣列；vector 預設用 0 初始化 / diff array, zero-initialised

        for (int i = 0; i < n / 2; ++i) {           // 走訪每組對稱配對 / loop over symmetric pairs
            int a = nums[i];                        // 左側元素 / left element
            int b = nums[n - 1 - i];                // 右側鏡像元素 / mirror element
            auto [lo, hi] = minmax(a, b);           // 結構化綁定 + minmax 一次取得小/大 / structured binding gets (min, max) at once

            d[lo + 1]         -= 1;                 // 進入 "只改一個" 區段，成本 2 → 1 / entering 1-move zone
            d[hi + limit + 1] += 1;                 // 離開 1-move 區段，成本 1 → 2 / leaving 1-move zone
            d[lo + hi]        -= 1;                 // 抵達 "剛好相加" 點，成本 1 → 0 / hitting 0-move point
            d[lo + hi + 1]    += 1;                 // 離開 0-move 點，成本 0 → 1 / leaving 0-move point
        }

        int ans = n;                                // 最壞情況上界 / upper bound: 2 moves per pair
        int cur = n;                                // f(x) 的累加器，基線為 n / running cost, baseline = n
        for (int x = 2; x <= 2 * limit; ++x) {      // 範圍式 for 也可以；這裡用索引較直觀 / index loop is clearer here
            cur += d[x];                            // 累加差分 = 前綴和 / prefix sum
            ans = min(ans, cur);                    // 取最小 / take minimum
        }
        return ans;                                 // 結束時 vector 會自動釋放 / vector cleans itself up
    }
};

複雜度 / Complexity

• Time: O(n + limit) — 我們對每組配對做 4 個 O(1) 的差分更新（共 O(n)），再對長度 2·limit + 2 的差分陣列做一次線性掃描（O(limit)）。Each of the n/2 pairs triggers four O(1) diff updates, then a single linear scan over the diff array of length 2·limit + 2.
• Space: O(limit) — 差分陣列大小為 2·limit + 2；除此之外只用幾個整數變數。The diff array dominates; only a constant number of scalars besides it.

Pitfalls & Edge Cases

• 差分索引越界 / Diff index out of range：hi + limit + 1 最大會到 2·limit + 1，所以 d 必須開到 2·limit + 2 大小，否則寫入會越界。d must have size 2·limit + 2 since hi + limit + 1 can reach 2·limit + 1.
• cur 的初始值 / Initial value of cur：用「每對都 2 次」當基線 (cur = n)，差分裡只記錄相對於基線的「節省」。如果忘了把基線設成 n，會得到負的答案。Start cur at n (the all-pairs-cost-2 baseline); the diffs only encode savings relative to that baseline — forgetting this yields negative numbers.
• 目標 x 的合法區間 / Valid range of x：x 只能落在 [2, 2·limit]；別把 x = 0 或 x = 1 算進來。Only scan x ∈ [2, 2·limit]; values below 2 or above 2·limit are unreachable.
• lo + 1 > 2·limit 等病態狀況 / Pathological positions：因為 lo ≤ hi ≤ limit，所以 lo+1 ≤ limit+1 ≤ 2·limit、lo+hi ≤ 2·limit、hi+limit+1 ≤ 2·limit+1，全部都在 d 的合法範圍內。All four written indices stay within bounds because lo, hi ≤ limit.
• 整數溢位 / Overflow：n ≤ 10^5、limit ≤ 10^5，所有中間值都是小整數，用 int 不會溢位。No risk: int is plenty given the constraints.
• 誤把 nums 中間元素重複算 / Double-counting middle pairs：迴圈是 i < n/2，每組配對只看一次；別寫成 i < n 否則會把每對算兩次。Loop bound is n/2, not n — otherwise each pair is counted twice.