leet1674.minimum-moves-to-make-array-complementary

给你一个长度为 偶数 n 的整数数组 nums 和一个整数 limit 。每一次操作，你可以将 nums 中的任何整数替换为 1 到 limit 之间的另一个整数。

如果对于所有下标 i（下标从 0 开始），nums[i] + nums[n - 1 - i] 都等于同一个数，则数组 nums 是 互补的 。例如，数组 [1,2,3,4] 是互补的，因为对于所有下标 i ，nums[i] + nums[n - 1 - i] = 5 。

返回使数组 互补 的 最少 操作次数。

示例 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 <= 105
• 1 <= nums[i] <= limit <= 105
• n 是偶数。

---

差分数组简介

这道题是我头一次领略到差分数组的威力。以往听到这个名词，总是敬而远之，不知道这是个啥东西，也有点畏惧接触。直到碰到这个科普帖子，

【算法小课堂】差分数组

才让我恍然大悟。原来差分数组就是离散函数的导数。早该知道到，差分的英文是differential，也有微分的意思。

• differential equations: 差分方程
• differentiable: 可微分的

我们回到离散数组$\{a_i{\}}_{i=1}^n$, 其差分数组定义为

$$d_i=\{\begin{array}{ll}{a}_1& \text{if}i=1\\ a_i-a_{i-1}& \text{if}i>1\end{array}$$

通俗理解就是，差分数组就是原数组相邻两项的增量构成的数组，并约定首项等于原数组首项。

研究差分数组主要因为它有一些性质。

性质1（积分）：从左到右累加差分数组中的元素，即可得到原数组。即，

$$\forall k\in [1,n],a_k=\sum _{i=1}^k{d}_i.$$

性质2：for $1\le i<j<n$ and $x\in N$, $\{a_k+x{\}}_{k=1}^j⟺d_i+x$, $d_{j+1}-x$.

说明，

1. 性质1就是离散积分的过程，因为差分数据是通过离散求导得到的，因此积分出来当然得到原函数。
2. 性质2将原数组的一个区间的操作，转换为差分数组上两个边界的操作。大大降低了算法复杂度。更通俗的描述，
   • 对原数组的子区间$[i,j]$, 将$a_i,a_{i+1},\dots ,a_j$都加上$x$. 等价于，
   • 把差分数组的$d_i$增加$x$，$d_{j+1}$减少$x$.

什么意思？利用性质2，我们可以原数组上对子区间的批量运算（$O(n)$）转换成差分数组上的两次运算（$O(1)$)，然后通过性质1复原数组。这在降低算法复杂度的时候非常有用！

思路

下面回到题目，题目有三个提示，其实合起来才是一个。

1. 对于给定的目标和x，每一对数据(a=nums[i], b=nums[n-1-i])要么变更0次，要么变更1次，要么变更2次，可以使得a+b=x.
2. 现在就要找这样的目标和，使得所有数据对变更次数加起来最少。
3. 创建一个差分数组来高效计算所有的变更次数。

这题比较可恶的是，遍历所有可能的目标和[2, 2*limit]，计算每个和对应的总变更次数，会超时。所以正好用上差分数组来降低复杂度。下面简要分析，

设a[i]表示目标和为i时，使得整个数组互补的变更次数。那么，

• 对于每一对数据(nums[i], nums[n-1-i])，记a为二者之小，b为二者之大。记目标和为x。
• 当$x\in [2,a]\cup [b+limit+1,2\ast limit]$，需要变更两次才能使得 a + b = x.
• 当$x\in [a+1,b+limit]$ 且 $x\ne a+b$ 时，需要变更一次。
• 当$x=a+b$ 时，需要变更0次。

现在我们遍历每一对数据，将a、b带入，然后对a[i]的相应子数组做上述加法。当遍历完所有数据对，a[i]也就构造好了，然后取最小值就可以。But，这样做会超时啊（$O(n\ast limit)$）！所以，我们取而代之，操作a[i]的差分数组，就可以把复杂度降到$O(n)$了呀。

Code

class Solution {
public:
    // see: https://leetcode.cn/problems/minimum-moves-to-make-array-complementary/solutions/3965634/chai-fen-shu-zu-pythonjavacgo-by-endless-efiv
    int minMoves(vector<int>& nums, int limit) {
        const int len = nums.size();
 
        // sum in [2, 2*limit]
        vector<int> diff(2 * limit + 2, 0);
 
        // fill the difference array
        for (int i = 0; i < len / 2; ++i) {
            int a = min(nums[i], nums[len - 1 - i]);
            int b = max(nums[i], nums[len - 1 - i]);
 
            // if sum in [2, a], we need 2 operations to make a + b = sum
            diff[2] += 2;
            diff[a + 1] -= 2;
 
            // if sum in [a+1, b+limit], we need 1 operation to make a + b = sum
            diff[a + 1] += 1;
            diff[b + limit + 1] -= 1;
 
            // if sum == a + b, we need 0 operation to make a + b = sum
            diff[a + b] -= 1;
            diff[a + b + 1] += 1;
 
            // if sum in [b+limit+1, 2*limit], we need 2 operations to make a + b = sum
            diff[b + limit + 1] += 2;
            // diff[2 * limit + 1] -= 2; // eliminate cause sum cannot be larger than 2*limit
        }
 
        // calc the partial sum
        int ans = INT_MAX, curr = 0;
        for (int i = 2; i <= 2 * limit; ++i) {
            curr += diff[i];
            ans = min(ans, curr);
        }
        return ans;
    }
};

参考

1. 题解 - 差分数组（Python/Java/C++/Go）