Question

You are given an integer array nums of even length n and an integer limit. In one move, you can replace any integer from nums with another integer between 1 and limit, inclusive.

The array nums is complementary if for all indices i (0-indexed), nums[i] + nums[n - 1 - i] equals the same number. For example, the array [1,2,3,4] is complementary because for all indices i, nums[i] + nums[n - 1 - i] = 5.

Return the minimum number of moves required to make nums complementary.

Example 1:

Input: nums = [1,2,4,3], limit = 4 Output: 1 Explanation: In 1 move, you can change nums to [1,2,2,3] (underlined elements are changed). 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. Therefore, nums[i] + nums[n-1-i] = 4 for every i, so nums is complementary. Example 2:

Input: nums = [1,2,2,1], limit = 2 Output: 2 Explanation: In 2 moves, you can change nums to [2,2,2,2]. You cannot change any number to 3 since 3 > limit. Example 3:

Input: nums = [1,2,1,2], limit = 2 Output: 0 Explanation: nums is already complementary.

Constraints:

n == nums.length 2 <= n <= 105 1 <= nums[i] <= limit <= 105 n is even.

Algorithm

题意是给定一个长度为偶数的数组，对于对于每一位nums[i]，都可以更改为[1, limit]，limit为给定值。问使整个数组每对nums[i]+nums[n-i-1]的和相等，最少需要更改几次。

我们按照分段函数来思考，假设a和b为一对，即nums[i]=a, nums[n-i-1]=b。首先如果什么都不改，即更改0次，我们得到a+b。如果更改一次，且往大了改，那么应该改变a，使它尽量变大，得到limit+b；如果往小了改，那么应该改变b，使它变小，最小为1，得到1+a。如果更改两次，往大了改，至少可以得到limit+b+1，即a变大，同时b变成比自己大1；同样的，如果往小了改，最小可以得到2，都改成1。于是我们得到了一下关键点：

[2, a]，要改2次；[a+1,a+b-1]，要改1次；a+b，要改0次；[a+b+1,limit+b]，要改1次；最后[limit+b+1, 2limit]要改2次。这里我们可以认为2limit是最大值因为constraints里面给了limit永远大于等于nums[i]。

因此重要的点在于2, a+1, a+b, a+b+1, limit+b+1，利用差分，假设原初始改动次数是0，从经过上述的点开始，改动次数分别+2(2)，-1(1)，-1(0)，+1(1)，+1(2)，括号中是当前实际要改的次数，这样就形成了分段函数。开一个大小为limit*2+2的数组，之后对于n/2对点，我们都计算这些点，对于数组上的这些点进行+或-次数的操作。计算这个数组的前缀和，找出最小的那一刻，即是答案。

Code

C++

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