写在前面

又是一周周赛题，很惨就写出了第一题，后边的不是超时就是不会做，感觉最近思路可能有点固化了，甚至第二题做过的栈都找不到思路了，还是需要多多复习呀。这道题是一道差分数组的应用，由于题目需要区间修改、单点查询，使用树状数组、线段树也可以求解，不过代码就会比较复杂，这里不过多解释了。

题目

核心思路

虽然说是使用差分数组，但是没做过这种题还是很难想到，所以我们不妨先从暴力解法开始寻找使用差分数组的方式。

暴力解法

class Solution {
    public int minMoves(int[] nums, int limit) {
        int n = nums.length;
        int res = n;
        for(int t = 2; t <= 2 * limit; t++){
            int target = 0;
            for(int i = 0; i < n - i; i++){
                int a = nums[i], b = nums[n - i - 1];
                if(t == a + b) continue;
                if(t >= Math.min(a, b) + 1 && t <= Math.max(a, b) +  limit){
                    target += 1;
                }else{
                    target += 2;
                }
            }
            res = Math.min(res, target);
        }
        return res;
    }
}

暴力法的核心思路就是枚举所有可能的和(nums[i] + nums[n - i - 1]) t，然后遍历原始数组，找到数组中每一对数对，计算其需要的操作次数即可。而操作次数有三种情况，参见下图 :

通过上图所示，可以将上述情况划分为区间表示 :

这样就可以解释的通暴力法了，暴力法时间复杂度为O(N * L)，N为数组长度，L为limit的值，对于给定的数据范围显然会超时，那么就必须寻找更优解。

优化方法

由于枚举的可能答案是连续的，在上述区间划分中，区间也是连续的，也就是说可以根据每一组(a, b)的值确定一个区间的划分[2, min(a, b) + 1)、[min(a, b) + 1, max(a, b) + limit]、(max(a, b) + limit, 2 * limit]，对于这三个区间的每个整数 t ，我们都可以通过上述方法知道 t 对应的答案应该加几(0 / 1 / 2)。那我们不妨拿一个数组将所有target的值存储起来，同时先枚举 nums 再枚举 target，得到如下代码：

class Solution {
    public int minMoves(int[] nums, int limit) {
        int n = nums.length;
        int[] target = new int[2 * limit + 1];
        for(int i = 0; i < n - i; i++){
            int a = nums[i], b = nums[n - i - 1];
            for(int t = 2; t < target.length; t++){
                if(t == a + b) continue;
                if(t >= Math.min(a, b) + 1 && t <= Math.max(a, b) +  limit){
                    target[t] += 1;
                }else{
                    target[t] += 2;
                }
            }
        }

        int res = n;
        for(int i = 2; i < target.length; i++){
            if(target[i] < res){
                res = target[i];
            }
        }
        return res;
    }
}

这样虽然也会超时，但是可以发现其中的这部分代码：

for(int t = 2; t < target.length; t++){
    if(t == a + b) continue;
    if(t >= Math.min(a, b) + 1 && t <= Math.max(a, b) +  limit){
       target[t] += 1;
    }else{
       target[t] += 2;
    }
}

恰好是进行区间更新的操作，而最终也只是求解目标数组每个位置的值，那么就可以使用差分数组进行优化，差分数组可以百度一下或者参考这里。

使用差分数组优化

class Solution {
    public int minMoves(int[] nums, int limit) {
        int n = nums.length;
        //差分数组
        int[] diff = new int[2 * limit + 2];
        for(int i = 0; i < n - i; i++){
            int a = nums[i], b = nums[n - i - 1];

            //[2, 2 * limit] += 2
            diff[2] += 2; diff[2 * limit + 1] -= 2;

            //[min(a, b) + 1, max(a, b) + limit] -= 1
            diff[Math.min(a, b) + 1] -= 1; diff[Math.max(a, b) + limit + 1] += 1;

            //[a + b] -= 1
            diff[a + b] -= 1; diff[a + b + 1] += 1;
        }

        int res = n;
        int sum = 0;
        for(int i = 2; i < diff.length - 1; i++){
            sum += diff[i];
            if(sum < res){
                res = sum;
            }
        }
        return res;
    }
}

由于差分数组进行的是区间更新，故先更新跨度大的区间，再更新其子区间要更方便一点，本质上还是划分之前的三种情况。
如果文章有写的不正确的地方还请指出，感恩相遇~