Leetcode 581. Shortest Unsorted Continuous Subarray

文章作者：Tyan
博客：noahsnail.com  |  CSDN  |  简书

1. Description

2. Solution

• Version 1

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        int start = 0;
        int end = nums.size() - 1;
        bool flag = false;
        for(int i = 0; i < nums.size(); i++) {
            for(int j = i + 1; j < nums.size(); j++) {
                if(nums[j] < nums[i]) {
                    flag = true;
                    break;
                }
            }
            if(flag) {
                start = i;
                break;
            }
        }
        if(!flag) {
            return 0;
        }
        flag = false;
        for(int i = nums.size() - 1; i >= start; i--) {
            for(int j = i - 1; j >= start; j--) {
                if(nums[j] > nums[i]) {
                    flag = true;
                    break;
                }
            }
            if(flag) {
                end = i;
                break;
            }
        }
        return end - start + 1;
    }
};

• Version 2

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        vector<int> copy(nums);
        sort(copy.begin(), copy.end());
        int start = 0;
        int end = nums.size() - 1;
        for(int i = 0; i < nums.size(); i++) {
            if(nums[i] == copy[i]) {
                start = i + 1;
            }
            else {
                break;
            }
        }
        if(start == nums.size()) {
            return 0;
        }
        for(int i = nums.size() - 1; i > start; i--) {
            if(nums[i] == copy[i]) {
                end = i - 1;
            }
            else {
                break;
            }
        }
        return end - start + 1;
    }
};

Reference

1. https://leetcode.com/problems/shortest-unsorted-continuous-subarray/description/