@[toc]

有序数组的平方

977. 有序数组的平方

• 双指针，找到正负交界处，向两边边界扫

// 977. 有序数组的平方
func sortedSquares(nums []int) []int {
    var res []int
    midIndex := 0
    for i := 0; i < len(nums); i++ {
        if nums[i] >= 0 {
            midIndex = i
            break
        }
        midIndex = i
    }
    // 双指针移动
    r := midIndex
    l := midIndex - 1
    for l >= 0 && r < len(nums) {
        if nums[l]*nums[l] > nums[r]*nums[r] {
            res = append(res, nums[r]*nums[r])
            r++
        } else {
            res = append(res, nums[l]*nums[l])
            l--
        }
    }
    // 扫尾
    for ; l >= 0; l-- {
        res = append(res, nums[l]*nums[l])
    }
    for ; r < len(nums); r++ {
        res = append(res, nums[r]*nums[r])
    }

    return res
}

• 双指针向中间夹逼（优化）

func sortedSquares(nums []int) []int {
    res := make([]int, len(nums))
    l := 0
    r := len(nums) - 1

    i := len(nums) - 1

    for i >= 0 {
        numl := nums[l] * nums[l]
        numr := nums[r] * nums[r]
        if numl < numr {
            res[i] = numr
            r--
        } else {
            res[i] = numl
            l++
        }
        i--
    }

    return res
}

长度最小的子数组

209. 长度最小的子数组

• 前缀和暴力法

func minSubArrayLen(target int, nums []int) int {
    res := 10000010
    // 前缀和记录
    sums := make([]int, len(nums)+1)
    sums[0] = 0
    sum := 0
    for i := 1; i <= len(nums); i++ {
        sum += nums[i-1]
        sums[i] = sum
    }

    // 计算差值S(r-l) = S(r) - S(l-1)

    for l := 1; l < len(sums); l++ {
        for r := l; r < len(sums); r++ {
            Snm := sums[r] - sums[l-1]
            if Snm >= target {
                res = min(res, r-l+1)
                break
            }
        }
    }
    if res == 10000010 {
        res = 0
    }
    return res
}

• 滑动窗口

func minSubArrayLen(target int, nums []int) int {
    res := 10000010

    l := 0
    r := 0
    sum := 0
    for r < len(nums) {
        sum += nums[r]
        if sum >= target {
            res = min(res, r-l+1)
            sum -= nums[l]
            sum -= nums[r] //细节，因为到下一个循环的时候又会在加一次nums[r]
            l++
        } else {
            r++
        }
    }
    if res == 10000010 {
        res = 0
    }
    return res
}

---

• 分类： 算法
• 标签： 算法基础 数组