Description:
https://leetcode.com/problems/shortest-unsorted-continuous-subarray/#/description
Algorithm:
Only need to care about the start index and end index
Code:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
class Solution { public: int findUnsortedSubarray(vector& nums) { if (nums.empty() || nums.size() == 1) { return 0; } int n = nums.size(); int cmin = nums[n - 1], indexmin = n - 1; for (int i = n - 1; i >= 0; --i) { if (nums[i] > cmin) { indexmin = i; } else { cmin = nums[i]; } } int cmax = nums[0], indexmax = 0; for (int i = 0; i < n; ++i) { if (nums[i] < cmax) { indexmax = i; } else { cmax = nums[i]; } } return indexmax > indexmin ? indexmax - indexmin + 1 : 0; } }; |
Time & Space:
O(n) & O(1)
|
1 |