2021-10-19:缺失的区间。给定一个排序的整数数组 nums ,其中元素的范围在 闭区间 [lower, upper] 当中,返回不包含在数组中的缺失区间。力扣163。

福大大 答案2021-10-19:

一次遍历。遍历的时候,修改左边界。 时间复杂度:O(N)。 空间复杂度:O(1)。

代码用golang编写。代码如下:

package main

import "fmt"

func main() {
    nums := []int{1, 2, 3, 4, 6, 8, 10}
    lower := 2
    upper := 10
    ret := findMissingRanges(nums, lower, upper)
    fmt.Println(ret)
}

func findMissingRanges(nums []int, lower int, upper int) []string {
    ans := make([]string, 0)
    for _, num := range nums {
        if num > lower {
            ans = append(ans, miss(lower, num-1))
        }
        if num == upper {
            return ans
        }
        lower = num + 1
    }
    if lower <= upper {
        ans = append(ans, miss(lower, upper))
    }
    return ans
}

// 生成"lower->upper"的字符串,如果lower==upper,只用生成"lower"
func miss(lower, upper int) string {
    left := fmt.Sprintf("%d", lower)
    right := ""
    if upper > lower {
        right = "->" + fmt.Sprintf("%d", upper)
    }
    return left + right
}

执行结果如下: 图片


左神java代码