581. Shortest Unsorted Continuous Subarray

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

Shortest Unsorted Continuous Subarray - LeetCode

 

문제 이해

입력으로 들어오는 배열에서 정렬되지 않은 구간을 찾는 문제

 

문제 접근

vector array를 하나를 추가 선언하고 정렬을 한다.

입력으로 들어온 nums array와 0부터 값이 다른 위치를 찾는다.

입력으로 들어온 nums array 와 n-1부터 값이 다른 위치를 찾는다.

끝 위치와 시작 위치 차이를 출력한다.

 

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        vector<int> arr = nums;
        sort(arr.begin(), arr.end());

        int st = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (arr[i] != nums[i])
                break;
            st++;
        }

        int ed = nums.size() - 1;

        for (int i = ed; i>=0; i--) {
            if (arr[i] != nums[i]) {
                ed = i;
                break;
            }
        }

        return ed - st + 1;
    }
};