LeetCode (C/C++) 581. Shortest Unsorted Continuous Subarray

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

---

풀이

토픽이 투포인터인 건 알았지만 풀이가 생각나지 않아 답지를 봤다.
1번 순회하며 앞에서부터는 최댓값, 뒤에서부터 최솟값을 찾는다.
maxVal을 업데이트하면서 nums[i] < maxVal인 경우, end를 갱신한다. 이는 nums[i]가 앞서 탐색한 요소들보다 작아 정렬이 필요하다는 의미이다.

마찬가지로 minVal은 뒤에서부터 탐색하며 begin을 갱신하며 최소 구간을 찾는다.

 

투포인터라 포인터 두 개로 탐색해야 한다고 생각했는데 특정 값을 저장하는 방식으로 사용하는 건 생각하지 못 했다.
어렵다...ㅠ

---

코드

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        // 정렬된 값이 들어왔을 때
        int begin = -1, end = -2;
        int size = nums.size();
        
        int maxVal = nums[0], minVal = nums[size - 1];

        for (int i = 0; i < size; i++) {
            maxVal = max(maxVal, nums[i]);
            minVal = min(minVal, nums[size - 1 - i]);

            // 정렬이 필요한 구간 구하기
            if (nums[i] < maxVal) end = i;
            if (nums[size - 1 - i] > minVal) begin = size - 1 - i;
        }
        return end - begin + 1;
    }
};