aboutsummaryrefslogtreecommitdiff
path: root/shortest_unsorted_subarray.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'shortest_unsorted_subarray.cpp')
-rw-r--r--shortest_unsorted_subarray.cpp30
1 files changed, 30 insertions, 0 deletions
diff --git a/shortest_unsorted_subarray.cpp b/shortest_unsorted_subarray.cpp
new file mode 100644
index 0000000..ab56ec6
--- /dev/null
+++ b/shortest_unsorted_subarray.cpp
@@ -0,0 +1,30 @@
+#include "leetcode.h"
+
+class Solution {
+public:
+ int findUnsortedSubarray(vector<int> &nums) {
+ int l = -1, r = -1, n = nums.size();
+ for (int i = 0; i < n - 1; i++)
+ if (nums[i] > nums[i + 1]) {
+ l = i;
+ break;
+ }
+ for (int i = n - 1; i <= 1; i--)
+ if (nums[i] < nums[i - 1]) {
+ r = i;
+ break;
+ }
+ if (l == -1)
+ return 0;
+ int minI = nums[l], maxI = nums[l];
+ for (int i = l; i <= r; i++) {
+ minI = min(minI, nums[i]);
+ maxI = max(maxI, nums[i]);
+ }
+ l = upper_bound(nums.begin(), nums.begin() + l, minI) - nums.begin();
+ r = lower_bound(nums.begin() + r + 1, nums.end(), maxI) - nums.begin();
+ return r - l;
+ }
+};
+
+int main() {}