LeetCode 581. Shortest Unsorted Contimuous Subarray

class Solution {
public:
   int findUnsortedSubarray(vector<int>& nums)
{
	vector<int> num_buffer;
	for (int i = 0; i < nums.size(); i++)
	{
		num_buffer.push_back(nums[i]);
	}
	int temp_i;
	
	for (int i = 0; i < nums.size(); i++)
	{
		for (int j = i+1; j < nums.size(); j++)
		{
			if (num_buffer[j] < num_buffer[i])
			{
				temp_i = num_buffer[j];
				num_buffer[j] = num_buffer[i];
				num_buffer[i] = temp_i;
			}
		}
	}
	int begin = 0;
	int end = 0;
	bool flag = true;
	for (int i = 0; i < nums.size(); i++)
	{
		if (nums[i] != num_buffer[i] && flag)
		{
			begin = i;
			flag = false;
		}
		else if (nums[i] != num_buffer[i])
		{
			end = i;
		}
	}
	if (begin != end)
		return (end - begin + 1);
	else
		return 0;
}
};

思路：先把数组进行排序，然后把排序完的数组和排序之前的数组进行比较。

solution上提供的一个解法，时间复杂度确实比我的解法小。

int findUnsortedSubarray(vector<int>& nums) {
        int shortest = 0;
        
        int left = 0, right = nums.size() - 1;
        while (left < nums.size() - 1 && nums[left] <= nums[left + 1]) { left++; }
        while (right > 0 && nums[right] >= nums[right - 1]) { right--; };
        
        if (right > left) {
            int vmin = INT_MAX, vmax = INT_MIN;
            for (int i = left; i <= right; ++i) {
                if (nums[i] > vmax) {
                    vmax = nums[i];
                }
                if (nums[i] < vmin) {
                    vmin = nums[i];
                }
            }
            
            while (left >= 0 && nums[left] > vmin) { left--; };
            while (right < nums.size() && nums[right] < vmax) { right++; };
            
            shortest = right - left - 1;
        }
        
        return shortest;
    }