Shortest Unsorted Continuous Subarray - LeetCode
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.
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
Constraints:
1 <= nums.length <= 104
-105 <= nums[i] <= 105
- code
class Solution:
def findUnsortedSubarray(self, nums: List[int]) -> int:
prev = nums[0]
end = 0
for i in range(len(nums)):
if nums[i] < prev: end = i
else: prev = nums[i]
start = len(nums) - 1
prev = nums[start]
for i in range(len(nums)-1, -1, -1):
if nums[i] > prev: start = i
else: prev = nums[i]
return end - start + 1 if end != 0 else 0
- code
class Solution {
public int findUnsortedSubarray(int[] nums) {
int istart = 0, iend = 0;
int n = nums.length;
// loop from left , find the big wrong index
int prev = nums[0];
for (int i = 0; i < n; i++){
if (nums[i] < prev) iend = i;
else prev = nums[i];
}
// loop from right, find the small wrong index
prev = nums[n - 1];
for (int i = n - 1; i >= 0; i--){
if (nums[i] > prev) istart = i;
else prev = nums[i];
}
return iend == 0 ? 0 : iend - istart + 1;
}
}