581. Shortest Unsorted Continuous Subarray / TypeScript

Given an integer array nums, you need to find one continuous subarray such that if you only sort this subarray in non-decreasing order, then the whole array will be sorted in non-decreasing order.

Return the shortest such subarray and output its length.

 

Example 1:

Input: nums = [2,6,4,8,10,9,15]
Output: 5
Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.

Example 2:

Input: nums = [1,2,3,4]
Output: 0

Example 3:

Input: nums = [1]
Output: 0

 

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

 

풀이 

function findUnsortedSubarray(nums: number[]): number {
    const len = nums.length;
    const sorted = [...nums].sort((a, b) => a - b);
    let [fIdx, bIdx] = [0, len - 1];
    
    for (; fIdx < len; fIdx++) if (nums[fIdx] !== sorted[fIdx]) break;
    if (fIdx === len) return 0; // nums is already sorted
    
    for (; bIdx >= 0; bIdx--) if (nums[bIdx] !== sorted[bIdx]) break;
    
    return bIdx - fIdx + 1;
};

 

주어진 배열 nums에서 정렬되지 않은 부분 배열의 길이를 찾는 함수 

1. 배열 길이 및 정렬된 배열 생성:
   • len 변수에 배열 nums의 길이를 저장
   • sorted 변수에 nums 배열을 오름차순으로 정렬한 새로운 배열을 저장.
2. 앞쪽에서부터 비교:
   • fIdx는 정렬이 필요하지 않은 앞쪽 인덱스를 나타내는 변수
   • fIdx를 0부터 시작하여, nums 배열과 sorted 배열을 비교하면서 nums[fIdx]가 sorted[fIdx]와 다른 첫 번째 위치를 찾음
   • 만약 fIdx가 len과 같다면, 배열 전체가 이미 정렬된 상태이므로 0을 반환.
3. 뒤쪽에서부터 비교:
   • bIdx는 정렬이 필요하지 않은 뒤쪽 인덱스를 나타내는 변수.
   • bIdx를 배열의 마지막 인덱스인 len - 1부터 시작하여, nums 배열과 sorted 배열을 비교하면서 nums[bIdx]가 sorted[bIdx]와 다른 첫 번째 위치를 찾음.
4. 정렬이 필요한 부분 배열의 길이 계산:
   • fIdx와 bIdx 사이의 길이를 계산하여 반환합니다.
   • bIdx - fIdx + 1이 정렬이 필요한 부분 배열의 길이

 

 

예시 [2, 6, 4, 8, 10, 9, 15] 

 

1. 배열 초기화 및 정렬:
   • nums = [2, 6, 4, 8, 10, 9, 15]
   • sorted = [2, 4, 6, 8, 9, 10, 15]
2. 앞쪽에서부터 비교:
   • fIdx = 0: nums[0]와 sorted[0]는 둘 다 2이므로 같아서 계속 진행.
   • fIdx = 1: nums[1]는 6이고, sorted[1]는 4입니다. 다르므로 여기서 중지합니다.
   • 결과: fIdx = 1
3. 뒤쪽에서부터 비교:
   • bIdx = 6: nums[6]와 sorted[6]는 둘 다 15이므로 같아서 계속 진행.
   • bIdx = 5: nums[5]는 9이고, sorted[5]는 10입니다. 다르므로 여기서 중지합니다.
   • 결과: bIdx = 5
4. 부분 배열 길이 계산:
   • bIdx - fIdx + 1 = 5 - 1 + 1 = 5

따라서, 주어진 배열에서 정렬이 필요한 부분 배열은 6, 4, 8, 10, 9이고, 이 부분 배열의 길이는 5