題目
難度：★★☆☆☆
類型：數(shù)組
給定一個整數(shù)數(shù)組蚯姆，你需要尋找一個連續(xù)的子數(shù)組沧侥，如果對這個子數(shù)組進行升序排序瞎疼，那么整個數(shù)組都會變?yōu)樯蚺判颉?/p>
你找到的子數(shù)組應是最短的，請輸出它的長度割卖。
說明
輸入的數(shù)組長度范圍在 [1, 10,000]前酿。
輸入的數(shù)組可能包含重復元素 ，所以升序的意思是<=究珊。
示例
示例 1:
輸入: [2, 6, 4, 8, 10, 9, 15]
輸出: 5
解釋: 你只需要對 [6, 4, 8, 10, 9] 進行升序排序薪者，那么整個表都會變?yōu)樯蚺判颉?/p>
解答
為了尋找需要排序的子串的最小長度，我們可以逆向思維剿涮，先將數(shù)組排序，然后從兩端向中間比較攻人，查看從哪個位置開始不一樣取试。
先將輸入數(shù)組排序，有必要判斷排序后的數(shù)組是否和原數(shù)組相同怀吻，如果相同說明無需排序任何子數(shù)組瞬浓，直接返回零即可；
定義左指針蓬坡，從零開始向右滑動猿棉，并逐一比較原數(shù)組和排序后數(shù)組在該指針處的值，遇到不同值時相當于遇到了需要排序的子數(shù)組的最左端屑咳，記錄下該位置并停止滑動萨赁；同樣的，定義從右向左滑動的右指針兆龙，記錄第一次出現(xiàn)不同的位置杖爽；
通過左右指針的位置即可計算出需要排序的最短無序子數(shù)組的長度，這里注意需要對結(jié)果進行+1即可紫皇。
class Solution:
def findUnsortedSubarray(self, nums):
sorted_nums = sorted(nums) # 排序后的結(jié)果
if sorted_nums == nums: # 如果輸入本來就有序
return 0 # 不需要排序任何元素
left = 0 # 初始化左指針
while True:
if nums[left] != sorted_nums[left]: # 遇到了第一個不同元素
break # 跳出循環(huán)
left += 1 # 左指針右移
right = len(nums) - 1 # 初始化右指針
while True:
if nums[right] != sorted_nums[right]: # 遇到了第一個不同元素
break # 跳出循環(huán)
right -= 1 # 右指針左移
return right - left + 1 # 返回需要調(diào)整的子串長度
下面是一個上述方法的一個緊湊寫法：
class Solution:
def findUnsortedSubarray(self, nums):
# 記錄下原數(shù)組和排序后數(shù)組相應元素不同的所有位置慰安，并組成列表
diff = [i for i, (a, b) in enumerate(zip(nums, sorted(nums))) if a != b]
# 如果有不同元素，返回不同元素的最右端位置和最左端位置之差聪铺，否則返回零
return len(diff) and max(diff) - min(diff) + 1
如有疑問或建議化焕，歡迎評論區(qū)留言~
