LeetCode 1674. 使数组互补的最少操作次数（差分思想）

示例 1：
输入：nums = [1,2,4,3], limit = 4
输出：1
解释：经过 1 次操作，你可以将数组 nums 变成 [1,2,2,3]：
nums[0] + nums[3] = 1 + 3 = 4.
nums[1] + nums[2] = 2 + 2 = 4.
nums[2] + nums[1] = 2 + 2 = 4.
nums[3] + nums[0] = 3 + 1 = 4.
对于每个 i ，nums[i] + nums[n-1-i] = 4 ，所以 nums 是互补的。

示例 2：
输入：nums = [1,2,2,1], limit = 2
输出：2
解释：经过 2 次操作，你可以将数组 nums 变成 [2,2,2,2] 。
你不能将任何数字变更为 3 ，因为 3 > limit 。

示例 3：
输入：nums = [1,2,1,2], limit = 2
输出：0
解释：nums 已经是互补的。
 
提示：
n == nums.length
2 <= n <= 10^5
1 <= nums[i] <= limit <= 10^5
n 是偶数。

class Solution {
public:
    int minMoves(vector<int>& nums, int limit) {
        int n = nums.size();
        vector<int> delta(2*limit+2, 0);
        //差分数组
        for(int i = 0; i < n/2; i++)
        {
            int a = min(nums[i], nums[n-1-i]);
            int b = max(nums[i], nums[n-1-i]);
            delta[2] += 2;//初始为2次 [2, a+1)
            delta[1+a]--;// sum < 1+a 时2次。[a+1, a+b) 需要1次，差值-1
            delta[a+b]--;// sum = a+b 时 不需要操作 0，差值 -1
            delta[a+b+1]++; // [a+b+1, b+limit] 时，需要操作1次，差值 +1 
            delta[b+1+limit]++; // [b+limit+1, 2*limit] 时，需要操作2次，差值+1
        }
        int presum = 0, ans = n;
        for(int i = 2; i <= 2*limit; ++i) 
        {
            presum += delta[i];
            ans = min(ans, presum);
        }
        return ans;
    }
};