題目

給你一個(gè)整數(shù)數(shù)組 nums ，你需要找出一個(gè) 連續(xù)子數(shù)組 ，如果對(duì)這個(gè)子數(shù)組進(jìn)行升序排序，那么整個(gè)數(shù)組都會(huì)變?yōu)樯蚺判颉?/p>

站在用戶的角度思考問題，與客戶深入溝通，找到桐柏網(wǎng)站設(shè)計(jì)與桐柏網(wǎng)站推廣的解決方案，憑借多年的經(jīng)驗(yàn)，讓設(shè)計(jì)與互聯(lián)網(wǎng)技術(shù)結(jié)合，創(chuàng)造個(gè)性化、用戶體驗(yàn)好的作品，建站類型包括：成都網(wǎng)站設(shè)計(jì)、網(wǎng)站制作、外貿(mào)營銷網(wǎng)站建設(shè)、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣、主機(jī)域名、網(wǎng)絡(luò)空間、企業(yè)郵箱。業(yè)務(wù)覆蓋桐柏地區(qū)。

請(qǐng)你找出符合題意的 最短 子數(shù)組，并輸出它的長度。

思路

方法一：雙指針 + 排序

最終目的是讓整個(gè)數(shù)組有序，那么可以先將數(shù)組拷貝一份進(jìn)行排序，然后使用兩個(gè)指針i和j分別找到左右兩端第一個(gè)不同的地方，那么[i,j]這一區(qū)間即是答案

java代碼如下：

class Solution {public int findUnsortedSubarray(int[] nums) {int n = nums.length;
        int[] arr = nums.clone();//java中的clone對(duì)于一維數(shù)組是深拷貝，重新分配空間，并將元素復(fù)制過去，對(duì)clone后的數(shù)組進(jìn)行修改不會(huì)影響源數(shù)組。但是對(duì)二維數(shù)組是淺拷貝，復(fù)制的是引用，實(shí)際上指向的是同一個(gè)地址，對(duì)拷貝的二維數(shù)組修改或者排序都會(huì)影響原二維數(shù)組
        Arrays.sort(arr);
        int i = 0, j = n - 1;
        while (i<= j && nums[i] == arr[i]) i++;
        while (i<= j && nums[j] == arr[j]) j--;
        return j - i + 1;
    }
}

方法二：雙指針 + 線性掃描（一次遍歷）

將整個(gè)數(shù)組分成三段處理，一次遍歷

正常排序(1 2 3 4 5): 左邊所有元素的大值(2)<= 每個(gè)元素(例如3)<= 右邊所有元素的最小值(4)

求解: 2 6 8 10 4 9 15
其中:
從左到右 9是最后一個(gè)小于 (左邊所有元素大值)的
從右到左 6是最后一個(gè)大于 (右邊所有元素最小值)的

故解為求:

• 從左到右遍歷, 記錄當(dāng)前遍歷數(shù)的大值, 最后一個(gè)小于大值的即 需要倒置數(shù)組的右邊邊界索引
• 從右到左遍歷, 記錄當(dāng)前遍歷數(shù)的最小值, 最后一個(gè)大于最小值的即 需要倒置數(shù)組的左邊邊界索引

java代碼如下（算法有點(diǎn)晦澀難懂，建議跟著例子在紙上走一遍）：

class Solution{public int findUnsortedSubarray(int[] nums) {int length = nums.length;
        int leftDiff = -1;
        int rightDiff = -1;
        //大值是順序遍歷使用的(求需排序數(shù)組的右邊邊界索引rightDiff), 也可以取Integer.MIN_VALUE
        int max = nums[0];
        //最小值是倒序遍歷使用的(求需排序數(shù)組的左邊邊界索引leftDiff), 也可以取Integer.MAX_VALUE
        int min = nums[length - 1];
        for (int i = 0; i< length; i++) {//順序執(zhí)行, 判斷 當(dāng)前值是否小于 已遍歷的大值, 是的話屬于需排序的數(shù)組元素, 替換rightDiff; 否就更新大值
            if (nums[i]< max){rightDiff = i;
            } else {max = nums[i];
            }
            //倒序執(zhí)行, 判斷 當(dāng)前值是否大于 已遍歷的最小值, 是的話屬于需排序的數(shù)組元素, 替換leftDiff; 否就更新最小值
            int index = length - 1 - i;
            if (nums[index] >min){leftDiff = index;
            } else {min = nums[index];
            }
        }
        return leftDiff != -1 ? rightDiff - leftDiff + 1 : 0;
    }
}

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)站題目：LeetCodeHOT100——581.最短無序連續(xù)子數(shù)組-創(chuàng)新互聯(lián)
瀏覽地址：http://aaarwkj.com/article16/gjpgg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供品牌網(wǎng)站制作、面包屑導(dǎo)航、電子商務(wù)、網(wǎng)站收錄、網(wǎng)站策劃、微信小程序

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)