【Leetcode】581. Shortest Unsorted Continuous Subarray

Description

Given an integer array, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order, too.

You need to find the shortest such subarray and output its length.

Example

Input: [2, 6, 4, 8, 10, 9, 15]
Output: 5
Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.

Note

1.Then length of the input array is in range [1, 10,000].
2.The input array may contain duplicates, so ascending order here means <=.

Solution

First

public int findUnsortedSubarray(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(i, nums[i]);
        }
        Arrays.sort(nums);
        Map<Integer, Integer> map1 = new HashMap<>();
        for (int j = 0; j < nums.length; j++) {
            map1.put(j, nums[j]);
        }
        int n = 0;
        while (n < map.size() && map.get(n).equals(map1.get(n))) {
        //while (map.get(n).equals(map1.get(n)) && n < map.size()) {
            n++;
        }
        if (nums.length > n + 1) {
            int m = nums.length - 1;
            int count = 0;
            while ( m >= 0 && map.get(m).equals(map1.get(m))) {
                m--;
                count++;
            }
            return nums.length - n - count;
        }
        return nums.length - n;
    }

Result

Analyse

就是两个map往中间减，然后统计个数，但是有几个需要总结的点。在最后写出。

Optimization

First

public int findUnsortedSubarray(int[] nums) {
        int len = nums.length;
        int max = nums[0];
        int min = nums[len - 1];
        int end = -2;
        int begin = -1;
        for (int i = 1; i < len; i++) {
            max = Math.max(max, nums[i]);
            min = Math.min(min, nums[len - 1 - i]);
            if (max > nums[i]) {
                end = i;
            }
            if (min < nums[len - 1 - i]) {
                begin = len - 1 - i;
            }
        }
        return end - begin + 1;
    }

Analyse

这个就是两边一直推，左边开始一直判断max，右边开始一直判断min，如果max或者min一直是边界值，那么刚好走到最后判断0，否则就确定要切割的边界。这里很取巧的办法就是从index小的开始判断max，从index大的开始判断min，这样O(n)思路清晰，一气呵成。

Second

public int findUnsortedSubarray_(int[] nums) {
        int len = nums.length;
        int[] temp = nums.clone();
        Arrays.sort(temp);
        int start = 0;
        int end = nums.length - 1;
        while (start < len && nums[start] == temp[start]) {
            start++;
        }
        while (end > start && nums[end] == temp[end]) {
            end--;
        }
        return end - start + 1;
    }

Analyse

这个就是我的解法的简化版本，这里需要注意的是第二个while里，直接加上判断是end>start而不是end>0之类，这样可以避免多算边界，很简单。

Summary

这里需要提醒自己的是日常代码的解法，一定要想清楚>和>=的不同，而且i+1和i的对于边界区别，不然很容易出现越界。
Map的书写过程中注释的那一行是

1	while (map.get(n).equals(map1.get(n)) && n < map.size()) {

这一行之所以要标注出来，有两点，一个是这个判断条件即使失败，也会先走map.get(n).equals(map1.get(n))这步，如果没有这个key，很容易报NullPointerException，所以一定要把n<map.size()写在前面。
细节决定成败。