减少 Go 中数字求和代码的处理时间

Question

我写了这段代码，但是代码测试站点由于处理时间而被拒绝。为了减少时间，我使用了双指针算法和 Goroutine（我不确定我是否正确使用了它）。但该网站仍然以同样的理由拒绝了。有什么改进方案可以通过这个吗？我怎样才能减少处理时间。请查看我的代码。感谢您的支持！

问题描述

N 个数字的序列 A[1], A[2], … , A[N] 存在。这个序列A[i]+A[i+1]+...中i到j的数之和写一个程序求+A[j-1]+A[j]变成M的情况的个数.

输入

第一行给出了N(1≤N≤10,000)和M(1≤M≤300,000,000)。下一行包含 A[1], A[2], … , A[N] 给定，以空格分隔。每个A[x]都是不超过30000的自然数。

打印

第一行的案例数。

例子

输入 1 :

4 2

1 1 1 1
输出 1:

3
输入 2 :

10 5

1 2 3 4 2 5 3 1 1 2
输出 2 :

3

package main

import "fmt"

func main() {
    var n int //numbers
    var m int //target sum

    c := make(chan []int)
    d := make(chan int)

    fmt.Scanf("%d %d\n", &n, &m)
    arr := make([]int, n)
    go ReadN(arr, n, c)
    go checker(<-c, n, m, d)
    fmt.Print(<-d)
}

func ReadN(arr []int, n int, c chan<- []int) {
    for i := 0; i < n; i++ {
        fmt.Scan(&arr[i])
    }
    c <- arr
}

func checker(arr []int, n, m int, d chan<- int) {
    var start int
    var end int
    var sum int
    var result int

    for start < n {
        if sum > m || end == n {
            sum -= arr[start]
            start++
        } else {
            sum += arr[end]
            end++
        }
        if sum == m {
            result++
        }
    }
    d <- result
}

Answer 1

问题来自 Scan 和 Scanf。它不做任何缓冲，如果您获得大量输入，它会变得非常慢。所以我把所有的Scan、Scanf都改成了Fscan、Fscanf。相反，我使用了 bufio 包。但是，如果您对使用 Fscanf() 的速度不满意，您应该认真考虑使用扫描仪。请参阅下面的代码。

package main

import (
    "bufio"
    "fmt"
    "os"
)

func main() {
    var n int //numbers
    var m int //target sum
    var bufin *bufio.Reader = bufio.NewReader(os.Stdin)

    fmt.Fscanf(bufin, "%d %d\n", &n, &m)
    arr := make([]int, n)
    arr = ReadN(arr, n, bufin)
    result := checker(arr, n, m)
    fmt.Print(bufout, result)
}

func ReadN(arr []int, n int, bufin *bufio.Reader) []int {
    for i := 0; i < n; i++ {
        fmt.Fscan(bufin, &arr[i])
    }
    return arr
}

func checker(arr []int, n, m int) int {
    var start int
    var end int
    var sum int
    var result int

    for start < n {
        if sum > m || end == n {
            sum -= arr[start]
            start++
        } else {
            sum += arr[end]
            end++
        }
        if sum == m {
            result++
        }
    }
    return result
}

Answer 2

您可以使用 prefix-sum 算法解决此类问题，该算法可以在 O(n) 时间和 space 内完成。也可以参考这个article.

有关此类问题的练习，请参阅this

减少 Go 中数字求和代码的处理时间

Reducing the process time of the sum of numbers code in Go

arrays

time

go

goroutine