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

Question

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

问题描述

N 个数的序列 A[1], A[2], ... , A[N] 存在。在这个序列中从 i 到 j 的数字之和 A[i]+A[i+1]+... 编写程序求 +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] 是一个不超过 30,000 的自然数。

打印

第一行的病例数。

例子

• 输入 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() 的速度也不满意，您应该认真考虑使用 Scanner。请参见下面的代码。package mainimport (&nbsp; &nbsp; "bufio"&nbsp; &nbsp; "fmt"&nbsp; &nbsp; "os")func main() {&nbsp; &nbsp; var n int //numbers&nbsp; &nbsp; var m int //target sum&nbsp; &nbsp; var bufin *bufio.Reader = bufio.NewReader(os.Stdin)&nbsp; &nbsp; fmt.Fscanf(bufin, "%d %d\n", &n, &m)&nbsp; &nbsp; arr := make([]int, n)&nbsp; &nbsp; arr = ReadN(arr, n, bufin)&nbsp; &nbsp; result := checker(arr, n, m)&nbsp; &nbsp; fmt.Print(bufout, result)}func ReadN(arr []int, n int, bufin *bufio.Reader) []int {&nbsp; &nbsp; for i := 0; i < n; i++ {&nbsp; &nbsp; &nbsp; &nbsp; fmt.Fscan(bufin, &arr[i])&nbsp; &nbsp; }&nbsp; &nbsp; return arr}func checker(arr []int, n, m int) int {&nbsp; &nbsp; var start int&nbsp; &nbsp; var end int&nbsp; &nbsp; var sum int&nbsp; &nbsp; var result int&nbsp; &nbsp; for start < n {&nbsp; &nbsp; &nbsp; &nbsp; if sum > m || end == n {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; sum -= arr[start]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; start++&nbsp; &nbsp; &nbsp; &nbsp; } else {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; sum += arr[end]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; end++&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; if sum == m {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; result++&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; return result}

Answer 2

您可以使用前缀和算法解决此类问题，该算法可以在 O(n) 时间和空间内完成。你也可以参考这篇文章。有关此类问题的练习，请参阅此