Leetcode 581. Shortest Unsorted Continuous Subarray

Tyan

发布于 2019-05-25 22:21:32

3220

发布于 2019-05-25 22:21:32

文章被收录于专栏：SnailTyan

文章作者：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;
    }
};