寫(xiě)在前面

又是一周周賽題混槐，很慘就寫(xiě)出了第一題编兄，后邊的不是超時(shí)就是不會(huì)做，感覺(jué)最近思路可能有點(diǎn)固化了声登，甚至第二題做過(guò)的棧都找不到思路了狠鸳，還是需要多多復(fù)習(xí)呀。這道題是一道差分?jǐn)?shù)組的應(yīng)用悯嗓，由于題目需要區(qū)間修改件舵、單點(diǎn)查詢，使用樹(shù)狀數(shù)組脯厨、線段樹(shù)也可以求解铅祸，不過(guò)代碼就會(huì)比較復(fù)雜，這里不過(guò)多解釋了合武。

題目

核心思路

雖然說(shuō)是使用差分?jǐn)?shù)組临梗，但是沒(méi)做過(guò)這種題還是很難想到，所以我們不妨先從暴力解法開(kāi)始尋找使用差分?jǐn)?shù)組的方式稼跳。

暴力解法

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盟庞，然后遍歷原始數(shù)組，找到數(shù)組中每一對(duì)數(shù)對(duì)汤善，計(jì)算其需要的操作次數(shù)即可茫经。而操作次數(shù)有三種情況巷波，參見(jiàn)下圖 :

優(yōu)化方法

由于枚舉的可能答案是連續(xù)的遂黍，在上述區(qū)間劃分中终佛，區(qū)間也是連續(xù)的，也就是說(shuō)可以根據(jù)每一組(a, b)的值確定一個(gè)區(qū)間的劃分[2, min(a, b) + 1)雾家、[min(a, b) + 1, max(a, b) + limit]铃彰、(max(a, b) + limit, 2 * limit]，對(duì)于這三個(gè)區(qū)間的每個(gè)整數(shù) t 芯咧，我們都可以通過(guò)上述方法知道 t 對(duì)應(yīng)的答案應(yīng)該加幾(0 / 1 / 2)牙捉。那我們不妨拿一個(gè)數(shù)組將所有target的值存儲(chǔ)起來(lái)，同時(shí)先枚舉 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;
    }
}

這樣雖然也會(huì)超時(shí)邪铲，但是可以發(fā)現(xiàn)其中的這部分代碼：

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;
    }
}

恰好是進(jìn)行區(qū)間更新的操作，而最終也只是求解目標(biāo)數(shù)組每個(gè)位置的值无拗，那么就可以使用差分?jǐn)?shù)組進(jìn)行優(yōu)化带到，差分?jǐn)?shù)組可以百度一下或者參考這里。

使用差分?jǐn)?shù)組優(yōu)化

class Solution {
    public int minMoves(int[] nums, int limit) {
        int n = nums.length;
        //差分?jǐn)?shù)組
        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;
    }
}

由于差分?jǐn)?shù)組進(jìn)行的是區(qū)間更新英染，故先更新跨度大的區(qū)間揽惹，再更新其子區(qū)間要更方便一點(diǎn)，本質(zhì)上還是劃分之前的三種情況四康。
如果文章有寫(xiě)的不正確的地方還請(qǐng)指出搪搏，感恩相遇~