题解 | #牛牛的数组匹配#

• 暴力

package main

import (
	"fmt"
)

func abs(n int) int {
	if n < 0 {
		return -n
	}
	return n
}

func Solve(a, b []int) []int {
	sum, n := 0, len(b)
	s := make([]int, n)
	tb := make([][]int, n)
	for i := 0; i < n; i++ {
		tb[i] = make([]int, n)
	}

	for _, v := range a {
		sum += v
	}
	s[0] = b[0]
	for i := 1; i < n; i++ {
		s[i] = s[i-1] + b[i]
	}
	min := abs(sum - b[0])
	l, r := 0, 0
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			if i == j {
				tb[i][j] = b[i]
			} else if i == 0 {
				tb[i][j] = s[j]
			} else if j > i {
				tb[i][j] = s[j] - s[i-1]
			}
			if abs(sum-tb[i][j]) < min {
				min = abs(sum - tb[i][j])
				l = i
				r = j
			}
		}
	}
	return b[l : r+1]
}

func main() {
	var n, m int
	fmt.Scan(&n, &m)
	a := make([]int, n)
	b := make([]int, m)
	for i := 0; i < n; i++ {
		fmt.Scan(&a[i])
	}
	for i := 0; i < m; i++ {
		fmt.Scan(&b[i])
	}
	res := Solve(a, b)
	for _, v := range res {
		fmt.Printf("%d ", v)
	}
}

• 前缀和+双指针

package main

import (
	"fmt"
	"math"
)

func abs(n int) int {
	if n < 0 {
		return -n
	}
	return n
}

func main() {
	var n, m, a, sum int
	fmt.Scan(&n, &m)
	b := make([]int, m)
	for i := 0; i < n; i++ {
		fmt.Scan(&a)
		sum += a
	}
	for i := 0; i < m; i++ {
		fmt.Scan(&b[i])
		// 特判
		if b[i] == sum {
			fmt.Println(b[i])
			return
		}
	}

	s := make([]int, m+1)
	// b 的 前缀和, 递增, 因为 b 中的元素是正数
	s[0] = 0
	for i := 1; i <= m; i++ {
		s[i] = s[i-1] + b[i-1]
	}
	// 特判
	if m == 1 || s[m] <= sum {
		for _,v := range b {
			fmt.Printf("%d ", v)
		}
		return
	}

	l, r, bl, br := 0, 1, 0, 0
	min := math.MaxInt
	for l < r && r <= m {
		d := s[r] - s[l]
		if abs(d-sum) < min {
			min = abs(d - sum)
			bl = l
			br = r
		}
		if d < sum {
			r++
		}
		if d > sum {
			l++
		}
	}

	for i := bl; i < br; i++ {
		fmt.Printf("%d ", b[i])
	}
}