寫在前面

又是一周周賽題，很慘就寫出了第一題，后邊的不是超時就是不會做，感覺最近思路可能有點固化了，甚至第二題做過的棧都找不到思路了，還是需要多多復(fù)習(xí)呀。這道題是一道差分?jǐn)?shù)組的應(yīng)用，由于題目需要區(qū)間修改、單點查詢，使用樹狀數(shù)組、線段樹也可以求解，不過代碼就會比較復(fù)雜，這里不過多解釋了。

題目

核心思路

雖然說是使用差分?jǐn)?shù)組，但是沒做過這種題還是很難想到，所以我們不妨先從暴力解法開始尋找使用差分?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ù)組中每一對數(shù)對，計算其需要的操作次數(shù)即可。而操作次數(shù)有三種情況，參見下圖 :

優(yōu)化方法

由于枚舉的可能答案是連續(xù)的，在上述區(qū)間劃分中，區(qū)間也是連續(xù)的，也就是說可以根據(jù)每一組(a, b)的值確定一個區(qū)間的劃分[2, min(a, b) + 1)、[min(a, b) + 1, max(a, b) + limit]、(max(a, b) + limit, 2 * limit]，對于這三個區(qū)間的每個整數(shù) t ，我們都可以通過上述方法知道 t 對應(yīng)的答案應(yīng)該加幾(0 / 1 / 2)。那我們不妨拿一個數(shù)組將所有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;
    }
}

這樣雖然也會超時，但是可以發(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;
    }
}

恰好是進行區(qū)間更新的操作，而最終也只是求解目標(biāo)數(shù)組每個位置的值，那么就可以使用差分?jǐn)?shù)組進行優(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ù)組進行的是區(qū)間更新，故先更新跨度大的區(qū)間，再更新其子區(qū)間要更方便一點，本質(zhì)上還是劃分之前的三種情況。
如果文章有寫的不正確的地方還請指出，感恩相遇~