[Leetcode][Java] 581 Shortest Unsorted Continuous Subarray

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.

 

integer 배열인 nums가 주어진다.

하나의 연속적인 sub배열을 구해라,

그 sub배열의 조건은 오직 그 sub배열을 정렬했을 때 전체 배열이 오름차순으로 정렬되는 것이다.

가장 짧은 sub 배열의 길이를 반환해라.

---

배열에 해당하는 문제이다.

풀이 방식으로는 두개의 포인터를 맨 앞 맨뒤에 두고,

하나씩 순회하면서 정렬기준에 맞지 않는 인덱스를 찾으면 된다.

맨 처음 포인터의 경우, 뒤에 값이 앞에 값보다 작아지는 순간부터의 최솟값의 인덱스를 찾으면 된다.

후에 해당 인덱스의 값이 배열에 어느 위치로 정렬되어야 하는지 찾아야 한다.

 

맨 뒤의 포인터도 위의 방식과 유사하게 진행하면 된다.

    public int findUnsortedSubarray(int[] nums) {
        boolean found = false;
        int min = Integer.MIN_VALUE;
        for (int i = 1; i <= nums.length - 1; i++) { // find minimum

            if (!found) {
                if (nums[i] < nums[i - 1]) {
                    found = true;
                    min = nums[i];
                }
            } else { // find minimum
                if (min >= nums[i]) {
                    min = nums[i];
                }
            }
        }

        int l = 0;
        if (!found) {
            return 0;
        } else { // find start index
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] > min) {
                    break;
                }
                l++;
            }
        }

        found = false;
        int max = Integer.MAX_VALUE;
        for (int i = nums.length - 2; i >= 0; i--) {
            if (!found) {
                if (nums[i] > nums[i + 1]) {
                    found = true;
                    max = nums[i];
                }
            } else {
                if (max <= nums[i]) {
                    max = nums[i];
                }
            }
        }
        int h = nums.length - 1;

        for (int i = nums.length - 1; i >= 0; i--) {
            if (nums[i] < max) {
                break;
            }
            h--;
        }

        return h - l + 1;
    }

 

해당 풀이로는 시간 복잡도는 O(n), 공간 복잡도는 O(1)이다.