209. Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn't one, return 0 instead.

Example:

Input: s = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: the subarray [4,3] has the minimal length under the problem constraint.

Follow up:
If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).

题目的大意是，在一个数组中找出一个可能的最短子数组，约束是子数组和大于某个值。

这道题可以用双指针的思路来解决，用两个指针来维护一个移动窗口，每次移动“前指针”后，移动“后指针”使得窗口满足约束，由此遍历所有可能的“前指针”情况，比较得出最优解。下面用go实现这个思路，

func Min(xs ...int) int {
    min := math.MaxInt32
    for _, x := range xs {
        if min > x {
            min = x
        }
    }
    return min
}

//209. Minimum Size Subarray Sum
func minSubArrayLen(sum int, nums []int) (ans int) {
    var start, end, tmpSum int
    ans = math.MaxInt32
    for start < len(nums) {
        //move 'end' to make slide window valid
        for end < len(nums) && tmpSum < sum {
            tmpSum += nums[end]
            end++
        }
        if tmpSum < sum {
            break
        } //not able to find a valid sliding window
        ans = Min(ans, end-start)
        //move slide window by increase 'start'
        tmpSum -= nums[start]
        start++
    }

    if ans == math.MaxInt32 {
        ans = 0
    }
    return
}

最后测试代码

Success

[Details](https://leetcode.com/submissions/detail/226806349/)

Runtime: 4 ms, faster than 100.00% of Go online submissions for Minimum Size Subarray Sum.

Memory Usage: 3.9 MB, less than 42.86% of Go online submissions for Minimum Size Subarray Sum.

1004. Max Consecutive Ones III

Given an array A of 0s and 1s, we may change up to K values from 0 to 1.

Return the length of the longest (contiguous) subarray that contains only 1s.

Example 1:

Input: A = [1,1,1,0,0,0,1,1,1,1,0], K = 2
Output: 6
Explanation:
[1,1,1,0,0,1,1,1,1,1,1]
Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.

Example 2:

Input: A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
Output: 10
Explanation:
[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.

Note:

1 <= A.length <= 20000
0 <= K <= A.length
A[i] is 0 or 1

题目的大意是在一个 01数组中要求出一个最长的子数组子数组中最多有K个0。

和上一道题类似，我们也可以用移动窗来维持一个拥有 K个0的子窗口，求出最优解，

func Max(xs ...int) int {
    max := math.MinInt32
    for _, x := range xs {
        if max < x {
            max = x
        }
    }
    return max
}

func longestOnes(ones []int, k int) (ans int) {
    var start, end, zeros int
    for ; end < len(ones); end++ {
        if ones[end] == 0 {
            zeros++
        }
        //move 'start' util zeros are equal or less than k
        for zeros > k {
            //remove the head element, if it is zeros, reduce
            // num of zero in sliding window
            if ones[start] == 0 {
                zeros--
            }
            start++
        }
        ans = Max(ans, end-start+1)
    }
    return
}

最后测试代码

Success

[Details](https://leetcode.com/submissions/detail/226807560/)

Runtime: 76 ms, faster than 33.33% of Go online submissions for Max Consecutive Ones III.

Memory Usage: 7.6 MB, less than 100.00% of Go online submissions for Max Consecutive Ones III.