[LeetCode]Shortest Unsorted Continuous Subarray

我们可以明确一点，只要存在reverse pair，那么reverse pair这个区间就都要被sorting。因为我们只sort一次，所以如果有多个reverse pair的话，我们取左右边界。我们首先从左到右遍历，记录扫过的最大值，并且更新reverse pair右边界。然后反向扫一次记录左边界。时间复杂度O(n)，常数空间，代码如下：

	class Solution {
	public:
	int findUnsortedSubarray(vector<int>& nums) {
	int len = nums.size(), first = -1, last = -1, currMax = nums[0], currMin = nums[len - 1];
	//find first and last reverse pairs
	for(int i = 1; i < len; ++i)
	{
	if(nums[i] < currMax)
	last = i;
	currMax = max(currMax, nums[i]);
	}
	for(int i = len - 2; i >= 0; --i)
	{
	if(nums[i] > currMin)
	first = i;
	currMin = min(currMin, nums[i]);
	}
	return first == -1 && last == -1? 0: last - first + 1;
	}
	};

view raw Shortest Unsorted Continuous Subarray.cpp hosted with ❤ by GitHub