牛客NC209 最短无序连续子数组【中等 数组，双指针 C++/Java/Go/PHP】

题目

题目链接：
https://www.nowcoder.com/practice/d17f4abd1d114617b51e951027be312e

思路

解题思路
1、方法1，排序对比：将数组按升序排序，然后与原数组对照，
         从哪里开始变化到哪里结束变化的数组就是答案。
2、 方法2，别人的代码：效率更高，时间复杂度O(n)，空间复杂度O(1)。但很难想到，
下面的答案里注释处提供了该代码

参考答案C++

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型vector
     * @return int整型
     */
    int findUnsortedSubarray(vector<int>& nums) {
        /*
          二、解题思路
          1、方法，排序对比：将数组按升序排序，然后与原数组对照，
             从哪里开始变化到哪里结束变化的数组就是答案。
          2、 方法，别人的代码：效率更高，时间复杂度O(n)，空间复杂度O(1)。但很难想到
        */

        int n = nums.size();
        vector<int> bak(n);
        for (int k = 0; k < n; k++) {
            bak[k] = nums[k];
        }
        int left = -1;
        int right = -1;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < n; i++) {
            if (left == -1 && nums[i] != bak[i]) {
                left = i;
            }
            if (right == -1 && nums[n - i - 1] != bak[n - i - 1]) {
                right = n - i - 1;
            }
        }

        if ( right == -1 ) {
            return 0;
        } else {
            return right - left + 1;
        }

        /*
                 2、 方法，别人的代码：效率更高，时间复杂度O(n)，空间复杂度O(1)。但很难想到
                    //双指针
                    //我们实际上需要找到的边界就是从左往右，找到比左边最大值还小的最右下标，
                    //从右往左，找到比右边最小值还大的最左下标。
                    //https://www.cnblogs.com/xqmeng/p/15093340.html
                class Solution {
                public:
                    int findUnsortedSubarray(vector<int>& nums) {
                        int n = nums.size();
                        int maxn = INT_MIN, right = -1;
                        int minn = INT_MAX, left = -1;
                        for (int i = 0; i < n; i++) {
                            if (maxn > nums[i]) {
                                right = i;
                            } else {
                                maxn = nums[i];
                            }
                            if (minn < nums[n - i - 1]) {
                                left = n - i - 1;
                            } else {
                                minn = nums[n - i - 1];
                            }
                        }
                        return right == -1 ? 0 : right - left + 1;
                    }
                };
        */
    }
};

参考答案Java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @return int整型
     */
    public int findUnsortedSubarray (int[] nums) {
        int n = nums.length;
        int[] bak = new int[n];
        for (int i = 0; i < n ; i++) {
            bak[i] = nums[i];
        }

        Arrays.sort(nums);
        int left = -1, right = -1;
        for (int i = 0; i < n ; i++) {
            if (left == -1 && nums[i] != bak[i]) {
                left = i;
            }

            if (right == -1 && nums[n - i - 1] != bak[n - i - 1]) {
                right = n - i - 1;
            }
        }

        return right == -1 ? 0 : right - left + 1;
    }


    public int f2(int[]
                  nums) { //别人的代码，最优解。时间复杂度O(n)，空间复杂度O(1)。但很难想到
        //双指针
        //我们实际上需要找到的边界就是从左往右，找到比左边最大值还小的最右下标，
        //从右往左，找到比右边最小值还大的最左下标。
        //https://www.cnblogs.com/xqmeng/p/15093340.html
        int n = nums.length;
        int maxn = 0x80000000, right = -1;
        int minn = 0x7fffffff, left = -1;
        for (int i = 0; i < n; i++) {
            if (maxn > nums[i]) {
                right = i;
            } else {
                maxn = nums[i];
            }

            if (minn < nums[n - i - 1]) {
                left = n - i - 1;
            } else {
                minn = nums[n - i - 1];
            }
            //System.out.println(i+":  left="+left+",right="+right+" maxn="+maxn+",minn="+minn);
        }

        return right == -1 ? 0 : right - left + 1;
    }
}

参考答案Go

package main

import "sort"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param nums int整型一维数组
 * @return int整型
 */
func findUnsortedSubarray(nums []int) int {
	/*
	   二、解题思路
	   1、方法，排序对比：将数组按升序排序，然后与原数组对照，
	      从哪里开始变化到哪里结束变化的数组就是答案。
	   2、 方法，别人的代码：效率更高，时间复杂度O(n)，空间复杂度O(1)。但很难想到
	*/

	n := len(nums)
	bak := make([]int, n)
	for k, v := range nums {
		bak[k] = v
	}
	left := -1
	right := -1
	sort.Ints(nums)
	for i := 0; i < n; i++ {
		if left == -1 && nums[i] != bak[i] {
			left = i
		}
		if right == -1 && nums[n-i-1] != bak[n-i-1] {
			right = n - i - 1
		}
	}

	if right == -1 {
		return 0
	} else {
		return right - left + 1
	}

	/*
			 2、 方法，别人的代码：效率更高，时间复杂度O(n)，空间复杂度O(1)。但很难想到
				//双指针
		        //我们实际上需要找到的边界就是从左往右，找到比左边最大值还小的最右下标，
		        //从右往左，找到比右边最小值还大的最左下标。
				//https://www.cnblogs.com/xqmeng/p/15093340.html
			class Solution {
			public:
			    int findUnsortedSubarray(vector<int>& nums) {
			        int n = nums.size();
			        int maxn = INT_MIN, right = -1;
			        int minn = INT_MAX, left = -1;
			        for (int i = 0; i < n; i++) {
			            if (maxn > nums[i]) {
			                right = i;
			            } else {
			                maxn = nums[i];
			            }
			            if (minn < nums[n - i - 1]) {
			                left = n - i - 1;
			            } else {
			                minn = nums[n - i - 1];
			            }
			        }
			        return right == -1 ? 0 : right - left + 1;
			    }
			};
	*/
}

参考答案PHP

<?php


/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param nums int整型一维数组 
 * @return int整型
 */
function findUnsortedSubarray( $nums )
{
    /*
    二、解题思路
    1、方法，排序对比：将数组按升序排序，然后与原数组对照，
       从哪里开始变化到哪里结束变化的数组就是答案。
    2、 方法，别人的代码：效率更高，时间复杂度O(n)，空间复杂度O(1)。但很难想到
 */
    $bak = [];
    foreach ($nums as $k=>$v){
        $bak[$k] = $v;
    }

    sort($nums);

    $left =-1;
    $right =-1;

    for($i=0;$i<count($nums);$i++){
        if($left ==-1 && $nums[$i]!=$bak[$i]){
            $left = $i;
        }

        if($right ==-1 &&$nums[count($nums)-$i-1] !=$bak[count($bak)-$i-1]){
            $right = count($nums)-$i-1;
        }
    }
    if($right ==-1){
        return 0;
    }else{
        return $right -$left+1;
    }

	/*
			 2、 方法，别人的代码：效率更高，时间复杂度O(n)，空间复杂度O(1)。但很难想到
				//双指针
		        //我们实际上需要找到的边界就是从左往右，找到比左边最大值还小的最右下标，
		        //从右往左，找到比右边最小值还大的最左下标。
	            //https://www.cnblogs.com/xqmeng/p/15093340.html
			class Solution {
			public:
			    int findUnsortedSubarray(vector<int>& nums) {
			        int n = nums.size();
			        int maxn = INT_MIN, right = -1;
			        int minn = INT_MAX, left = -1;
			        for (int i = 0; i < n; i++) {
			            if (maxn > nums[i]) {
			                right = i;
			            } else {
			                maxn = nums[i];
			            }
			            if (minn < nums[n - i - 1]) {
			                left = n - i - 1;
			            } else {
			                minn = nums[n - i - 1];
			            }
			        }
			        return right == -1 ? 0 : right - left + 1;
			    }
			};
	*/
}