LeetCode-最短无序连续子数组

yfx

August 3, 2021

711 views

No comments

1349 words

算法 C/C++ Python

<div class="tip share">请注意，本文编写于 1390 天前，最后修改于 1375 天前，其中某些信息可能已经过时。</div>

# Problem - [最短无序连续子数组](https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray/)

> **分析：**
>
> 要找到符合要求的数组那么数组可以分为`numsA`, `numsB`, `numsC`三个部分，那么我们可以把原数组排序得到有序版，然后两个数组一一比对分别便能找到$[left,right]$符合要求的区间
>
> **算法：**
>
> 排序+双指针

## 方法一：DFS

### 参考代码：

<div class="tab-container post_tab box-shadow-wrap-lg">
<ul class="nav no-padder b-b scroll-hide" role="tablist">
<li class='nav-item active' role="presentation"><a class='nav-link active' style="" data-toggle="tab" 
aria-controls='tabs-fc7598cb5530c5875034ae6c889e922d670' role="tab" data-target='#tabs-fc7598cb5530c5875034ae6c889e922d670'>**C++**</a></li><li class='nav-item ' role="presentation"><a class='nav-link ' style="" data-toggle="tab" 
aria-controls='tabs-25510615da3e67e5b21de13935e473bf381' role="tab" data-target='#tabs-25510615da3e67e5b21de13935e473bf381'>**Python 3**</a></li>
</ul>
<div class="tab-content no-border">
<div role="tabpanel" id='tabs-fc7598cb5530c5875034ae6c889e922d670' class="tab-pane fade active in">

```cpp
class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        if (is_sorted(nums.begin(), nums.end())) return 0;
        vector<int> numsSorted(nums);
        sort(numsSorted.begin(), numsSorted.end());
        int lo = 0;
        while (numsSorted[lo] == nums[lo]) ++ lo;
        int hi = nums.size() - 1;
        while (numsSorted[hi] == nums[hi]) -- hi;
        return hi - lo + 1;
    }
};
```

</div><div role="tabpanel" id='tabs-25510615da3e67e5b21de13935e473bf381' class="tab-pane fade  ">

```python
class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        n = len(nums)

def is_sorted():
            for i in range(1, n):
                if nums[i - 1] > nums[i]: return False
            return True
  
        if is_sorted(): return 0
        lo, hi = 0, n - 1
        numsSorted = sorted(nums)
        while numsSorted[lo] == nums[lo]: lo += 1
        while numsSorted[hi] == nums[hi]: hi -= 1
        return hi - lo + 1
```

</div>
</div>
</div>

### 复杂度分析：

* 时间复杂度：$O(n)$
* 空间复杂度：$O(1)$

Last modification：August 18, 2021