581. Shortest Unsorted Continuous Subarray

Leetcode link

解题思路——排序

• TC: O(n * log(n))
• SC: O(n)

本题要求我们找出一个未排序数组的最长已排序连续子数组

既然是这样，那我们可以直接用一个相同的数组，经过排序之后分别从左边跟右边寻找第一个不相同的元素然后计算元素之间的距离就好

C++

class Solution {
 public:
  int findUnsortedSubarray(vector<int>& nums) {
    vector<int> sortedNums(nums);
    sort(sortedNums.begin(), sortedNums.end());
    int left = 0, right = nums.size() - 1;
    while ((left < (nums.size() - 1)) && (sortedNums[left] == nums[left])) {
      left++;
    }
    while ((right >= 0) && (sortedNums[right] == nums[right])) {
      right--;
    }
    int res = right - left + 1;
    return res > 0 ? res : 0;
  }
};

Javascript

var findUnsortedSubarray = function(nums) {
    let sortedNums = [...nums];
    sortedNums.sort((a,b)=>a-b);
    let left = 0, right = nums.length - 1;
    while ((left < (nums.length - 1)) && (sortedNums[left] === nums[left])) {
      left++;
    }
    while ((right >= 0) && (sortedNums[right] === nums[right])) {
      right--;
    }
    let res = right - left + 1;
    return res > 0 ? res : 0;
};

解题思路——逻辑

• TC: O(n)
• SC: O(1)

我们也可以用逻辑推导出问题的答案：

1. 首先我们先从左往右找第一个不是升序的元素，从这个元素开始，找出剩余数组的最小值，记为 minimum
2. 然后我们从右往左找第一个不是降序的元素，从这个元素开始，找出剩余数组的最大值，记为 maximun
3. 接着我们从左往右遍历数组，这次的目标是找到第一个比 minimum 大的元素，其下标记作 k
4. 我们再从右往左遍历数组，找到第一个比 maximum 小的元素，其下标记作 l
5. 求 l 与 k 之间的距离，就是我们的答案

C++

class Solution {
 public:
  int findUnsortedSubarray(vector<int>& nums) {
    int maximun = INT_MIN, minimum = INT_MAX;
    int len = nums.size();
    bool flag = false;
    for (int i = 1; i < len; i++) {
      if (nums[i - 1] > nums[i]) {
        flag = true;
      }
      if (flag) {
        minimum = min(nums[i], minimum);
      }
    }
    flag = false;
    for (int j = len - 2; j >= 0; j--) {
      if (nums[j] > nums[j + 1]) {
        flag = true;
      }
      if (flag) {
        maximun = max(nums[j], maximun);
      }
    }
    int k, l;
    for (k = 0; k < len; k++) {
      if (nums[k] > minimum) {
        break;
      }
    }
    for (l = len - 1; l >= 0; l--) {
      if (nums[l] < maximun) {
        break;
      }
    }
    return l - k < 0 ? 0 : l - k + 1;
  }
};

Javascript

var findUnsortedSubarray = function(nums) {
    let maximun = Number.MIN_SAFE_INTEGER, minimum = Number.MAX_SAFE_INTEGER;
    let len = nums.length;
    let flag = false;
    for (let i = 1; i < len; i++) {
      if (nums[i - 1] > nums[i]) {
        flag = true;
      }
      if (flag) {
        minimum = Math.min(nums[i], minimum);
      }
    }
    flag = false;
    for (let j = len - 2; j >= 0; j--) {
      if (nums[j] > nums[j + 1]) {
        flag = true;
      }
      if (flag) {
        maximun = Math.max(nums[j], maximun);
      }
    }
    let k, l;
    for (k = 0; k < len; k++) {
      if (nums[k] > minimum) {
        break;
      }
    }
    for (l = len - 1; l >= 0; l--) {
      if (nums[l] < maximun) {
        break;
      }
    }
    return l - k < 0 ? 0 : l - k + 1;
  }