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
