var findUnsortedSubarray = function(nums) {
let left = nums.length,
right = 0
for (let i = 0; i < nums.length - 1; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[j] < nums[i]) {
right = Math.max(right, j)
left = Math.min(left, i)
}
}
}
return right - left < 0 ? 0 : right - left + 1
}
Runtime: 1356 ms, faster than 5.00% of JavaScript online submissions for Shortest Unsorted Continuous Subarray.
Memory Usage: 36.7 MB, less than 87.50% of JavaScript online submissions for Shortest Unsorted Continuous Subarray.
可惜效率极低
func max(a, b int) int {
if a > b {
return a
}
return b
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func findUnsortedSubarray(nums []int) int {
left, right := len(nums), 0
for i := 0; i < len(nums)-1; i++ {
for j := i + 1; j < len(nums); j++ {
if nums[j] < nums[i] {
right = max(right, j)
left = min(left, i)
}
}
}
if right-left < 0 {
return 0
} else {
return right - left + 1
}
}
Runtime: 1220 ms, faster than 5.43% of Go online submissions for Shortest Unsorted Continuous Subarray. Memory Usage: 6.2 MB, less than 100.00% of Go online submissions for Shortest Unsorted Continuous Subarray.
go也效率极慢
class Solution:
def findUnsortedSubarray(self, nums: List[int]) -> int:
left = len(nums)
right = 0
for I in range(len(nums) - 1):
for j in range(I + 1, len(nums)):
if nums[j] < nums[I]:
right = max(right, j)
left = min(left, i)
return 0 if (right - left < 0) else (right - left + 1)
python直接超时。。
排序
排序，然后比较不同的地方，就是答案了
var findUnsortedSubarray = function(nums) {
const sorted = nums.slice(0);
sorted.sort((a, b) => a - b)
let start = sorted.length,
end = 0
for (let i = 0; i < sorted.length; i++) {
if (sorted[i] != nums[i]) {
start = Math.min(start, i)
end = Math.max(end, i)
}
}
return (end - start >= 0 ? end - start + 1 : 0)
}
Runtime: 96 ms, faster than 58.10% of JavaScript online submissions for Shortest Unsorted Continuous Subarray. Memory Usage: 39.3 MB, less than 12.50% of JavaScript online submissions for Shortest Unsorted Continuous Subarray.
func max(a, b int) int {
if a > b {
return a
}
return b
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func findUnsortedSubarray(nums []int) int {
sorted := make([]int, len(nums))
copy(sorted, nums)
sort.Ints(sorted)
start := len(sorted)
end := 0
for i, val := range sorted {
if val != nums[i] {
start = min(start, i)
end = max(end, i)
}
}
if end-start >= 0 {
return end - start + 1
} else {
return 0
}
}
Runtime: 44 ms, faster than 26.36% of Go online submissions for Shortest Unsorted Continuous Subarray. Memory Usage: 6.1 MB, less than 100.00% of Go online submissions for Shortest Unsorted Continuous Subarray.
class Solution:
def findUnsortedSubarray(self, nums: List[int]) -> int:
sort = nums.copy()
sort.sort()
start = len(sort)
end = 0
for i in range(len(sort)):
if sort[i] != nums[i]:
start = min(start, i)
end = max(end, i)
return 0 if (end - start < 0) else (end - start + 1)
Runtime: 256 ms, faster than 41.83% of Python3 online submissions for Shortest Unsorted Continuous Subarray. Memory Usage: 15.1 MB, less than 5.00% of Python3 online submissions for Shortest Unsorted Continuous Subarray.
双指针的另一种做法
var findUnsortedSubarray = function(nums) {
let start = -1,
end = -2,
min = nums[nums.length - 1],
max = nums[0]
for (let i = 0; i < nums.length; i++) {
let pos = nums.length - 1 - i
max = Math.max(max, nums[i])
min = Math.min(min, nums[pos])
if (nums[i] < max) {
end = i
}
if (nums[pos] > min) {
start = pos
}
}
return end - start + 1
}
Runtime: 68 ms, faster than 86.38% of JavaScript online submissions for Shortest Unsorted Continuous Subarray. Memory Usage: 37.1 MB, less than 75.00% of JavaScript online submissions for Shortest Unsorted Continuous Subarray.
class Solution:
def findUnsortedSubarray(self, nums: List[int]) -> int:
start = -1
end = -2
min_val = nums[len(nums) - 1]
max_val = nums[0]
for i in range(len(nums)):
pos = len(nums)-1-i
max_val = max(max_val, nums[i])
min_val = min(min_val, nums[pos])
if(nums[i] < max_val):
end = i
if(nums[pos] > min_val):
start = pos
return end-start+1
Runtime: 276 ms, faster than 22.72% of Python3 online submissions for Shortest Unsorted Continuous Subarray. Memory Usage: 15.2 MB, less than 5.00% of Python3 online submissions for Shortest Unsorted Continuous Subarray.
func max(a, b int) int {
if a > b {
return a
}
return b
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func findUnsortedSubarray(nums []int) int {
start := -1
end := -2
min_val := nums[len(nums)-1]
max_val := nums[0]
for i, val := range nums {
pos := len(nums) - 1 - i
max_val = max(max_val, val)
min_val = min(min_val, nums[pos])
if val < max_val {
end = i
}
if nums[pos] > min_val {
start = pos
}
}
return end - start + 1
}
Runtime: 36 ms, faster than 55.81% of Go online submissions for Shortest Unsorted Continuous Subarray. Memory Usage: 6.2 MB, less than 100.00% of Go online submissions for Shortest Unsorted Continuous Subarray.