###### tags: `Leetcode` `medium` `pointer` `sort` `python` `c++`

# 581. Shortest Unsorted Continuous Subarray

## [題目連結:] https://leetcode.com/problems/shortest-unsorted-continuous-subarray/description/

## 題目:
Given an integer array ```nums```, you need to find one **continuous subarray** that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order.

Return the shortest such subarray and output its length.

**Example 1:**

Input: nums = [2,6,4,8,10,9,15]
Output: 5
Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.

**Example 2:**

Input: nums = [1,2,3,4]
Output: 0

**Example 3:**

Input: nums = [1]
Output: 0

**Follow up**: Can you solve it in ```O(n)``` time complexity?

## 解題想法:
* 此題為給一數組，求出最短的連續數組長度，使得對該數組排序後，可以使得整串數組變得有序
* 使用pointer
* 先clone排序好nums: sortedNums
* 分別從頭尾比對nums、sortedNums:
* 分別找遇到頭尾第一個遇到不同的數字位置
* 即為距離
* follow up還沒進行研究~

## Python:

class Solution(object):
    def findUnsortedSubarray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        #先排序好
        sortedNums=sorted(nums)
        head=0
        tail=0
        #從頭找第一個不同的
        for i in range(len(nums)):
            if nums[i]!=sortedNums[i]:
                head=i
                break
        #從尾找第一個不同的
        for i in range(len(nums)-1, -1, -1):
            if nums[i]!=sortedNums[i]:
                tail=i
                break
        return (tail-head+1) if head!=tail else 0

result=Solution()
nums = [2,6,4,8,10,9,15]
ans=result.findUnsortedSubarray(nums)
print(ans)

## C++:

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        vector<int> sortedNums=nums;
        sort(sortedNums.begin(), sortedNums.end());
        int head=0, tail=0, n=nums.size();
        for (int i=0; i<n; i++){
            if (nums[i]!=sortedNums[i]){
                head=i;
                break;
            }
        }
        for (int j=n-1; j>=0; j--){
            if (nums[j]!=sortedNums[j]){
                tail=j;
                break;
            }
        }
        return (head!=tail)? (tail-head+1) : 0;
    }
};