写点什么

2023-12-20:用 go 语言,给定一个数组 arr,长度为 n,在其中要选两个不相交的子数组。 两个子数组的累加和都要是 T,返回所有满足情况中,两个子数组长度之和最小是多少? 如果没有有效方法,返回 -

  • 2023-12-20
    北京
  • 本文字数:2803 字

    阅读完需:约 9 分钟

2023-12-20:用 go 语言,给定一个数组 arr,长度为 n,在其中要选两个不相交的子数组。


两个子数组的累加和都要是 T,返回所有满足情况中,两个子数组长度之和最小是多少?


如果没有有效方法,返回-1。


正式 :


2 <= n <= 10^6


0 <= arr[i] <= 10000


1 <= T <= 10^8


扩展 :


2 <= n <= 10^6


-10000 <= arr[i] <= 10000


1 <= T <= 10^8


都能时间复杂度做到 O(N)。


来自字节。


答案 2023-12-20:


来自左程云


灵捷3.5

大体步骤如下:

Algorithm 1: minLenBothT1


1.初始化数组 arr 的累加和数组 sum,并计算 arr 的累加和。


2.初始化变量 ans 为一个较大的整数。


3.使用四重循环遍历所有可能的起始和结束索引组合(a, b, c, d)。


4.检查子数组[a, b]和[c, d]的累加和是否等于目标值 T。


5.如果满足条件,则更新 ans 为两个子数组长度之和的最小值。


6.如果 ans 的值没有被更新过,则返回-1,否则返回 ans。


Algorithm 2: minLenBothT2


1.初始化变量 ans 为一个较大的整数。


2.遍历数组 arr,寻找和为 0 的连续子数组,记录其长度为 cnt。


3.如果 cnt 大于等于 2,则返回 2 作为结果。


4.对于每个起始索引 l,从右侧扩展子数组的结束索引 r,使得子数组的和尽量接近目标值 T。


5.记录满足和为 T 的子数组的最小长度到 right[l]数组中。


6.从右到左遍历数组 arr,对于每个结束索引 r,从左侧缩小子数组的起始索引 l,使得子数组的和尽量接近目标值 T。


7.如果和为 T 且 right[r+1]不是无穷大,则更新 ans 为当前长度+r-l+right[r+1]的最小值。


8.如果 ans 的值没有被更新过,则返回-1,否则返回 ans。


Algorithm 3: minLenBothT3


1.初始化变量 ans 为一个较大的整数。


2.构建累加和出现次数的映射表 sums,初始时将 0 的索引设置为-1。


3.构建左侧最小长度的数组 left,初始时将所有元素设置为一个较大的整数。


4.遍历数组 arr,计算累加和 sum,并检查 sum-t 在 sums 中是否存在。


5.如果存在,则更新左侧最小长度 left[i]为当前索引 i 与 sums[sum-t]之差。


6.更新 sums[sum]为当前索引 i。


7.从左到右遍历 left 数组,将每个位置的值更新为其与前一个位置的较小值。


8.清空 sums 映射表,并将 0 的索引设置为数组 arr 的长度。


9.从右到左遍历数组 arr,计算累加和 sum,并检查 sum-t 在 sums 中是否存在且左侧最小长度 left[i-1]不是一个较大的整数。


10.如果满足条件,则更新 ans 为当前长度+sums[sum-t]-i 的最小值。


11.更新 sums[sum]为当前索引 i。


12.如果 ans 的值没有被更新过,则返回-1,否则返回 ans。


Algorithm 1:


  • 时间复杂度:O(n^4)

  • 空间复杂度:O(n)


Algorithm 2:


  • 时间复杂度:O(n)

  • 空间复杂度:O(n)


Algorithm 3:


  • 时间复杂度:O(n)

  • 空间复杂度:O(n)

go 语言完整代码如下:

package main
import ( "fmt" "math" "math/rand" "time")
func minLenBothT1(arr []int, t int) int { n := len(arr) sum := make([]int, n) sum[0] = arr[0] for i := 1; i < n; i++ { sum[i] = sum[i-1] + arr[i] } ans := math.MaxInt32 for a := 0; a < n-1; a++ { for b := a; b < n-1; b++ { for c := b + 1; c < n; c++ { for d := c; d < n; d++ { if sum1(a, b, sum) == t && sum1(c, d, sum) == t { ans = min(ans, b+d-a-c+2) } } } } } if ans == math.MaxInt32 { return -1 } return ans}
func sum1(l, r int, sum []int) int { if l == 0 { return sum[r] } return sum[r] - sum[l-1]}
func minLenBothT2(arr []int, t int) int { n := len(arr) if t < 0 { return -1 } if t == 0 { cnt := 0 for _, num := range arr { if num == 0 { cnt++ } } if cnt >= 2 { return 2 } return -1 } right := make([]int, n) for i := 0; i < n; i++ { right[i] = math.MaxInt32 } for l, r, sum := 1, 1, 0; l < n; l++ { r = max(r, l) for r < n && sum < t { sum += arr[r] r++ } if sum == t { right[l] = r - l } sum -= arr[l] } for i := n - 2; i >= 0; i-- { right[i] = min(right[i], right[i+1]) } ans := math.MaxInt32 for r, l, sum := n-2, n-2, 0; r >= 0; r-- { l = min(l, r) for l >= 0 && sum < t { sum += arr[l] l-- } if sum == t && right[r+1] != math.MaxInt32 { ans = min(ans, r-l+right[r+1]) } sum -= arr[r] } if ans == math.MaxInt32 { return -1 } return ans}
func minLenBothT3(arr []int, t int) int { n := len(arr) sums := make(map[int]int) sums[0] = -1 left := make([]int, n) for i := 0; i < n; i++ { left[i] = math.MaxInt32 } for i, sum := 0, 0; i < n-1; i++ { sum += arr[i] if l, found := sums[sum-t]; found { left[i] = i - l } sums[sum] = i } for i := 1; i < n-1; i++ { left[i] = min(left[i-1], left[i]) } ans := math.MaxInt32 sums = make(map[int]int) sums[0] = n for i, sum := n-1, 0; i >= 1; i-- { sum += arr[i] if _, found := sums[sum-t]; found && left[i-1] != math.MaxInt32 { ans = min(ans, left[i-1]+sums[sum-t]-i) } sums[sum] = i } if ans == math.MaxInt32 { return -1 } return ans}
func min(a, b int) int { if a < b { return a } return b}
func max(a, b int) int { if a > b { return a } return b}
func randomArray1(n, v int) []int { arr := make([]int, n) for i := 0; i < n; i++ { arr[i] = rand.Intn(v + 1) } return arr}
func randomArray2(n, v int) []int { arr := make([]int, n) for i := 0; i < n; i++ { arr[i] = rand.Intn(2*v+1) - v } return arr}
func main() { rand.Seed(time.Now().UnixMicro()) N := 100 V := 100 T := 100 testTimes := 10000 fmt.Println("正式方法测试开始") for i := 0; i < testTimes; i++ { n := rand.Intn(N) + 2 v := rand.Intn(V) + 1 arr := randomArray1(n, v) t := rand.Intn(T) ans1 := minLenBothT1(arr, t) ans2 := minLenBothT2(arr, t) if ans1 != ans2 { fmt.Println("出错了!") } } fmt.Println("正式方法测试结束")
fmt.Println("扩展方法测试开始") for i := 0; i < testTimes; i++ { n := rand.Intn(N) + 2 v := rand.Intn(V) + 1 arr := randomArray2(n, v) t := rand.Intn(T) ans1 := minLenBothT1(arr, t) ans3 := minLenBothT3(arr, t) if ans1 != ans3 { fmt.Println("出错了!") } } fmt.Println("扩展方法测试结束")}
复制代码



发布于: 刚刚阅读数: 5
用户头像

公众号:福大大架构师每日一题 2021-02-15 加入

公众号:福大大架构师每日一题

评论

发布
暂无评论
2023-12-20:用go语言,给定一个数组arr,长度为n,在其中要选两个不相交的子数组。 两个子数组的累加和都要是T,返回所有满足情况中,两个子数组长度之和最小是多少? 如果没有有效方法,返回-_福大大架构师每日一题_福大大架构师每日一题_InfoQ写作社区