天天看點

leetcode最短無序連續子數組

leetcode最短無序連續子數組

平民解法:

既然是找最小數組,那就得到一個排序好的數組,然後直接和初試數組比對,用一個left,right分别記錄從最初開始不同,到最後不同的小标,最後左右做差再加一,就能得到長度。

leetcode最短無序連續子數組

其他參考解法:

連結: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) 不確定有序。