2875-MinimumSizeSubarrayInInfiniteArray.go

package main

// 2875. Minimum Size Subarray in Infinite Array
// You are given a 0-indexed array nums and an integer target.

// A 0-indexed array infinite_nums is generated by infinitely appending the elements of nums to itself.

// Return the length of the shortest subarray of the array infinite_nums with a sum equal to target. 
// If there is no such subarray return -1.

// Example 1:
// Input: nums = [1,2,3], target = 5
// Output: 2
// Explanation: In this example infinite_nums = [1,2,3,1,2,3,1,2,...].
// The subarray in the range [1,2], has the sum equal to target = 5 and length = 2.
// It can be proven that 2 is the shortest length of a subarray with sum equal to target = 5.

// Example 2:
// Input: nums = [1,1,1,2,3], target = 4
// Output: 2
// Explanation: In this example infinite_nums = [1,1,1,2,3,1,1,1,2,3,1,1,...].
// The subarray in the range [4,5], has the sum equal to target = 4 and length = 2.
// It can be proven that 2 is the shortest length of a subarray with sum equal to target = 4.

// Example 3:
// Input: nums = [2,4,6,8], target = 3
// Output: -1
// Explanation: In this example infinite_nums = [2,4,6,8,2,4,6,8,...].
// It can be proven that there is no subarray with sum equal to target = 3.

// Constraints:
//     1 <= nums.length <= 10^5
//     1 <= nums[i] <= 10^5
//     1 <= target <= 10^9

import "fmt"

// // 解答错误 533 / 535 
// func minSizeSubarray(nums []int, target int) int {
//     inf := int(1e5)
//     res, sum, left, right, n := inf, nums[0], 0, 1, len(nums)
//     min := func (x, y int) int { if x < y { return x; }; return y; }
//     for right < inf {
//         if sum == target {
//             res = min(res, right - left)
//         }
//         if sum > target {
//             sum -= nums[left % n]
//             left++
//         } else {
//             sum += nums[right % n]
//             right++
//         }
//     }
//     if res >= inf {
//         return -1
//     }
//     return res
// }

func minSizeSubarray(nums []int, target int) int {
    a, b, n, sum, pre := 0,  1 << 31, len(nums), 0, 0
    for _, v := range nums {
        sum += v
    }
    if target > sum {
        a = n * (target / sum)
        target -= target / sum * sum
    }
    if target == sum {
        return n
    }
    min := func (x, y int) int { if x < y { return x; }; return y; }
    pos := map[int]int{0: -1}
    for i, v := range nums {
        pre += v
        if j, ok := pos[pre-target]; ok {
            b = min(b, i - j)
        }
        if j, ok := pos[pre - (sum - target)]; ok {
            b = min(b, n - (i - j))
        }
        pos[pre] = i
    }
    if b == 1 << 31 {
        return -1
    }
    return a + b
}

func minSizeSubarray1(nums []int, target int) int {
    sum, n := 0, len(nums)
    for _, v := range nums {
        sum += v
    }
    count := (target / sum) * n
    target = target % sum
    sum = 0
    res := n + 1
    min := func (x, y int) int { if x < y { return x; }; return y; }
    for i, j := 0, 0; j < n * 2; j++ {
        sum += nums[j % n]
        for i <= j && sum > target {
            sum -= nums[i%n]
            i++
        }
        if sum == target {
            res = min(res, j - i + 1) 
        }
    }
    if res == n + 1 {
        return -1
    }
    return res + count
}

func minSizeSubarray2(nums []int, target int) int {
    res, sum, n := 1 << 31, 0, len(nums)
    for _, v := range nums {
        sum += v
    }
    repeats := target / sum
    target = target % sum
    if target == 0 {
        return repeats * n
    }
    min := func (x, y int) int { if x < y { return x; }; return y; }
    left, subsum := 0, 0
    // Perform sliding window on 2x of nums
    for right := 0; right < 2 * n; right++ {
        subsum += nums[right%n]
        for left < right && subsum > target {
            subsum -= nums[left%n]
            left++
        }
        if subsum == target {
            res = min(res, right - left + 1)
        }
    }
    if res == 1 << 31 {
        return -1
    }
    return repeats * n + res
}

func main() {
    // Example 1:
    // Input: nums = [1,2,3], target = 5
    // Output: 2
    // Explanation: In this example infinite_nums = [1,2,3,1,2,3,1,2,...].
    // The subarray in the range [1,2], has the sum equal to target = 5 and length = 2.
    // It can be proven that 2 is the shortest length of a subarray with sum equal to target = 5.
    fmt.Println(minSizeSubarray([]int{1,2,3}, 5)) // 2
    // Example 2:
    // Input: nums = [1,1,1,2,3], target = 4
    // Output: 2
    // Explanation: In this example infinite_nums = [1,1,1,2,3,1,1,1,2,3,1,1,...].
    // The subarray in the range [4,5], has the sum equal to target = 4 and length = 2.
    // It can be proven that 2 is the shortest length of a subarray with sum equal to target = 4.
    fmt.Println(minSizeSubarray([]int{1,1,1,2,3}, 4)) // 2
    // Example 3:
    // Input: nums = [2,4,6,8], target = 3
    // Output: -1
    // Explanation: In this example infinite_nums = [2,4,6,8,2,4,6,8,...].
    // It can be proven that there is no subarray with sum equal to target = 3.
    fmt.Println(minSizeSubarray([]int{2,4,6,8}, 3)) // -1

    fmt.Println(minSizeSubarray([]int{1,2,3,4,5,6,7,8,9}, 3)) // 1
    fmt.Println(minSizeSubarray([]int{9,8,7,6,5,4,3,2,1}, 3)) // 1
    fmt.Println(minSizeSubarray([]int{1,1,1}, 1000000000)) // 1000000000

    fmt.Println(minSizeSubarray1([]int{1,2,3}, 5)) // 2
    fmt.Println(minSizeSubarray1([]int{1,1,1,2,3}, 4)) // 2
    fmt.Println(minSizeSubarray1([]int{2,4,6,8}, 3)) // -1
    fmt.Println(minSizeSubarray1([]int{1,2,3,4,5,6,7,8,9}, 3)) // 1
    fmt.Println(minSizeSubarray1([]int{9,8,7,6,5,4,3,2,1}, 3)) // 1
    fmt.Println(minSizeSubarray1([]int{1,1,1}, 1000000000)) // 1000000000

    fmt.Println(minSizeSubarray2([]int{1,2,3}, 5)) // 2
    fmt.Println(minSizeSubarray2([]int{1,1,1,2,3}, 4)) // 2
    fmt.Println(minSizeSubarray2([]int{2,4,6,8}, 3)) // -1
    fmt.Println(minSizeSubarray2([]int{1,2,3,4,5,6,7,8,9}, 3)) // 1
    fmt.Println(minSizeSubarray2([]int{9,8,7,6,5,4,3,2,1}, 3)) // 1
    fmt.Println(minSizeSubarray2([]int{1,1,1}, 1000000000)) // 1000000000
}