weekly contest 32的第一题。这题我一开始就想着把每个子串都拿出来sort一遍再放回去，跟sort完的对比一下。但是复杂度太高(O(n2)), TLE了(但是用熟了System.arraycopy(nums, 0, temp, 0, nums.length);这个方法。。)。 如下：
Approach 1: BRUTE FORCE(TIME LIMIT EXCEEDED)
public int findUnsortedSubarray(int[] nums) { if (nums == null || nums.length == 0) return 0; int sorted[] = new int[nums.length]; System.arraycopy(nums, 0, sorted, 0, nums.length); Arrays.sort(sorted); if (Arrays.equals(sorted, nums)) return 0; int minLen = nums.length; for (int i = 0; i < nums.length; i++) { for (int j = i + 1; j < nums.length; j++) { int temp[] = new int[nums.length]; System.arraycopy(nums, 0, temp, 0, nums.length); Arrays.sort(temp, i, j + 1); if (Arrays.equals(sorted, temp)) { minLen = Math.min(j + 1 - i, minLen); break; } } } return minLen; }复制代码 #Approach 2: Compare the sorted parts 从首位开始跟sort过的array相比。Time : O(nlogn)。
public int findUnsortedSubarray(int[] nums) { int [] temp = new int[nums.length]; System.arraycopy(nums,0 , temp , 0 , nums.length); Arrays.sort(temp); int start = 0 , end = nums.length -1 ; while (start< nums.length && temp[start] == nums[start] ){ start ++ ; } while (end> start && temp[end] == nums[end]){ end -- ; } return end + 1 - start; }复制代码 还看到有一种O(n)的，现在脑子晕了不想看了。
ref: https://discuss.leetcode.com/topic/89282/java-o-n-time-o-1-space https://discuss.leetcode.com/category/741/shortest-unsorted-continuous-subarray Java拷贝数组的几种方法： http://www.cnblogs.com/jjdcxy/p/5870524.html