假设 res[x] 表示的是，nums[i] + nums[n - 1 - i] 为 x 的时候，需要多少次操作。

我们只需要计算出所有的 x 对应的 res[x], 取最小值就好了。

根据题意，nums[i] + nums[n - 1 - i] 最小是 2，即将两个数都修改为 1；最大是 2 * limit，即将两个数都修改成 limit。

所以，res[x] 中 x 的取值范围是 [2, 2 * limit]。我们用一个 res[2 * limit + 1] 的数组就好。

关键是，如何求出每一个 res[x] 位置的值，即修改后互补的数字和为 x，需要多少操作？

为了叙述方便，假设 nums[i] 为 A；nums[n - 1 - i] 为 B。

显然有：

• 如果修改后两个数字的和是 A + B，我们使用的操作数是 0 (没有修改));

• 否则的话，如果修改后两个数字和在 [1 + min(A, B), limit + max(A, B)] 的范围，我们使用的操作数是 1 (只需要修改 A 或者 B 就好);

• 否则的话，如果修改后两个数字和在 [2, 2 * limit] 的范围，我们使用的操作数是 ``2`(两个数字都要修改));

所以，我们的算法是遍历每一组 nums[i] 和 nums[n - 1 - i]，然后：

• 先将 [2, 2 * limit] 的范围需要的操作数 + 2；

• 之后，将 [1 + min(A, B), limit + max(A, B)] 的范围需要的操作数 - 1（即 2 - 1 = 1，操作 1 次）；

• 之后，将 [A + B] 位置的值再 -1（即 1 - 1 = 0，操作 0 次）。

可以看出，整个过程都是在做区间更新。最后，我们查询每一个位置的值，取最小值就好。

对于这个需求，我们当然可以使用线段树或者树状数组解决，但代码量稍大，且复杂度也是 O(nlogn) 的。

但是仔细观察，我们发现，我们只需要作区间更新，和单点查询。

对于这个需求，有一种非常常规的”数据结构“，叫差分数组，完全满足需求，并且编程极其简单，整体可以在 O(n) 的时间解决。

打上引号，是因为差分数组就是一个数组而已。

简单来说，差分数组 diff[i]，存储的是 res[i] - res[i - 1]；而差分数组 diff[0...i] 的和，就是 res[i] 的值。

大家可以用一个小数据试验一下，很好理解。

如果我们想给 [l, r] 的区间加上一个数字 a, 只需要 diff[l] += a，diff[r + 1] -= a。

这样做，diff[0...i] 的和，就是更新后 res[i] 的值。

依然是，大家可以用一个小数据试验一下，其实很好理解。

有了差分数组这个武器，这个问题就很简单了。

我的参考代码如下（C++）：

class Solution {
public:
    int minMoves(vector<int>& nums, int limit) {
        
        // 差分数组, diff[0...x] 的和表示最终互补的数字和为 x，需要的操作数
        // 因为差分数组的计算需要更新 r + 1，所以数组的总大小在 limit * 2 + 1 的基础上再 + 1
        vector<int> diff(limit * 2 + 2, 0);

        int n = nums.size();
        for(int i = 0; i < n / 2; i ++){
            int A = nums[i], B = nums[n - 1 - i];

            // [2, 2 * limit] 范围 + 2
            int l = 2, r = 2 * limit;
            diff[l] += 2, diff[r + 1] -= 2;

            // [1 + min(A, B), limit + max(A, B)] 范围 -1
            l = 1 + min(A, B), r = limit + max(A, B);
            diff[l] += -1, diff[r + 1] -= -1;

            // [A + B] 再 -1    
            l = A + B, r = A + B;
            diff[l] += -1, diff[r + 1] -= -1;
        }

        // 依次求和，得到 最终互补的数字和 i 的时候，需要的操作数 sum
        // 取最小值
        int res = n, sum = 0;
        for(int i = 2; i <= 2 * limit; i ++){
            sum += diff[i];
            if(sum < res) res = sum;
        }
        return res;
    }
};

整体时间复杂度是 O(n) 的；空间复杂度也是 O(n) 的。

觉得有帮助请点赞哇！