
平民解法:
既然是找最小數組,那就得到一個排序好的數組,然後直接和初試數組比對,用一個left,right分别記錄從最初開始不同,到最後不同的小标,最後左右做差再加一,就能得到長度。
其他參考解法:
連結:https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray/solution/gong-shui-san-xie-yi-ti-shuang-jie-shuan-e1le/
雙指針 + 線性掃描
另外一個做法是,我們把整個數組分成三段處理。
起始時,先通過雙指針 ii 和 jj 找到左右兩次側滿足 單調遞增 的分割點。
即此時 [0, i][0,i] 和 [j, n)[j,n) 滿足升序要求,而中間部分 (i, j)(i,j) 不確定有序。