本场周赛题解 | 我的LeetCode比赛题解

我们考虑任意一个数对$(a,b)$，不妨假设$a\leq b$。假设最终选定的和值为$target$，则我们可以发现，对于$(a,b)$这个数对：

• 当$target<1+a$时，需要操作两次；
• 当$1+a\leq target<a+b$时，需要操作一次；
• 当$target=a+b$时，不需要操作；
• 当$a+b<target\leq b+limit$时，需要操作一次；
• 当$target>b+limit$时，需要操作两次。

我们设初始操作次数为两次。令$target$从数轴最左端开始向右移动，我们会发现：

• 在$1+a$处，操作次数减少一次；
• 在$a+b$处，操作次数减少一次；
• 在$a+b+1$处，操作次数增加一次；
• 在$b+limit+1$处，操作次数增加一次。

因此，我们可以遍历数组中的所有数对，求出每个数对的这四个关键位置，然后更新差分数组。最后，我们遍历（扫描）差分数组，就可以找到令总操作次数最小的$target$，同时可以得到最少的操作次数。

• 时间复杂度$O(N+L)$。
• 空间复杂度$O(L)$。

###cpp

class Solution {
public:
    int minMoves(vector<int>& nums, int limit) {
        int n = nums.size();
        vector<int> delta(limit * 2 + 2);
        for (int i = 0; i < n / 2; ++i) {
            int lo = 1 + min(nums[i], nums[n - i - 1]);
            int hi = limit + max(nums[i], nums[n - i - 1]);
            int sum = nums[i] + nums[n - i - 1];
            delta[lo]--;
            delta[sum]--;
            delta[sum + 1]++;
            delta[hi + 1]++;
        }
        int now = n;
        int ans = n;
        for (int i = 2; i <= limit * 2; ++i) {
            now += delta[i];
            ans = min(ans, now);
        }
        return ans;
    }
};