581. 最短无序连续子数组

àì夳堔傛蜴生んèń 2022-12-02 04:30 119阅读 0赞

# 题目： #

[581. 最短无序连续子数组][581.]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center]

# 题解：双向遍历 #

## 1. 解释一： ##

![在这里插入图片描述][20200830013423616.png_pic_center]  
![在这里插入图片描述][20200830013454691.png_pic_center]

## 2. 解释二： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 1]

## 3. 解释三： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 2]

## 4. 解释四： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 3]

# 代码：双向遍历 #

public class code581 { 
    
        public static int findUnsortedSubarray(int[] nums) { 
            int len = nums.length;
            if(len <= 1)
            { 
                return 0;
            }
    
            int left = len;
            int right = -1;
    
            int max = Integer.MIN_VALUE;
            int min = Integer.MAX_VALUE;
    
            for(int i = 0; i < len; i++)
            { 
                // 从左到右找出最后一个破坏递增的数
                if(nums[i] >= max)
                { 
                    max = nums[i];
                }
                else
                { 
                    right = i;
                }
                // 从右到左找出最后一个破坏递减的数
                if(nums[len - i - 1] <= min)
                { 
                    min = nums[len - i - 1];
                }
                else
                { 
                    left = len - i - 1;
                }
            }
    
            if(right > left)
            { 
                return right - left + 1;
            }
            else // 当给定的数组，默认就是升序的话，则不需要进行调整，子数组长度为 0
            { 
                return 0;
            }
        }
    
        public static void main(String[] args) { 
            int nums[] = {  2, 6, 4, 8, 10, 9, 15 };
            int res = findUnsortedSubarray(nums);
            System.out.println(res);
        }
    }

# 参考： #

1.  [最短无序连续子数组][Link 1]
2.  [581. 最短无序连续子数组][581. 1]
3.  [时间超过100%的Java解法：][100_Java]
4.  [两次遍历 + 排序比对 python3][_ _ python3]
5.  [Java 击败100% 时间复杂度O(N) 空间复杂度O(1)][Java _100_ _O_N_ _O_1]
6.  [最短无序连续子数组(O(1)空间)][O_1]
7.  [不排序实现。][Link 2]
8.  [总结了三种想法][Link 3]

[581.]: https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/6111a63650a44086913b6b10067eda77.png
[20200830013423616.png_pic_center]: /images/20221123/2e7d67c141794feaab60db6347bf0449.png
[20200830013454691.png_pic_center]: /images/20221123/074d66b0a1934a05b43431e44fce72dd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/3bc1a5b695e5425889667ce558275c85.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/91c03a3de54b4d0b906857b2313bf3e6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/9aa4b70af0294712814ece6897637f78.png
[Link 1]: https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray/solution/zui-duan-wu-xu-lian-xu-zi-shu-zu-by-leetcode/
[581. 1]: https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray/solution/581-zui-duan-wu-xu-lian-xu-zi-shu-zu-by-ming-zhi-s/
[100_Java]: https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray/solution/shi-jian-chao-guo-100de-javajie-fa-by-zackqf/
[_ _ python3]: https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray/solution/liang-ci-bian-li-pai-xu-bi-dui-python3-by-zhu_shi_/
[Java _100_ _O_N_ _O_1]: https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray/solution/java-ji-bai-100-shi-jian-fu-za-du-on-kong-jian-fu-/
[O_1]: https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray/solution/zui-duan-wu-xu-lian-xu-zi-shu-zu-o1kong-jian-by-ze/
[Link 2]: https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray/solution/bu-pai-xu-shi-xian-by-jin-mu-yan-3/
[Link 3]: https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray/solution/zong-jie-liao-san-chong-xiang-fa-by-xiaobaik/