英文:
Reducing the process time of the sum of numbers code in Go
问题
我写了这段代码,但是代码测试网站因为处理时间的原因拒绝了它。为了减少时间,我使用了双指针算法和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 //数字个数
var m int //目标和
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
}
英文:
I wrote this code, but the code test site rejected due to process time. To reduce time, I used Two pointers algorism, and Goroutine(I am not sure I used it correctly). But still that site rejected with the same reason. Is there any improvement solution to pass this? How can I reduce processing time.
Please review my code. Thank you for your support!
Problem description
sequence of N numbers A[1], A[2], … , A[N] exists. The sum of numbers from i to j in this sequence A[i]+A[i+1]+… Write a program to find the number of cases where +A[j-1]+A[j] becomes M.
input
In the first line, N(1≤N≤10,000) and M(1≤M≤300,000,000) are given. The next line contains A[1], A[2], … , A[N] is given, separated by spaces. Each A[x] is a natural number not exceeding 30,000.
the number of cases on the first line.
Example
-
input 1 :
4 2
1 1 1 1
-
output 1:
3
-
input 2 :
10 5
1 2 3 4 2 5 3 1 1 2
-
output 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
}
答案1
得分: 1
问题出在Scan和Scanf上。它们不进行任何缓冲,如果输入很多,会导致速度非常慢。所以我将所有的Scan和Scanf都改成了Fscan和Fscanf。另外,我使用了bufio包。然而,即使使用了Fscanf(),如果你对速度还不满意,你应该考虑使用Scanner。
以下是修改后的代码:
package main
import (
"bufio"
"fmt"
"os"
)
func main() {
var n int // 数字个数
var m int // 目标和
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
}
英文:
Problem was from Scan and Scanf. It doesn't do any buffering, which makes it very slow if you get a lot of input. So I changed all Scan, Scanf to Fscan, Fscanf. Instead, I used bufio package. However, if you are not satisfied with the speed even with Fscanf(), you should seriously consider using a Scanner.
See below code.
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
}
答案2
得分: 0
你可以使用前缀和算法来解决这种类型的问题,它可以在O(n)的时间和空间复杂度内完成。
你还可以参考这篇文章。
如果想在这种类型的问题上进行练习,可以参考这个。
英文:
You can solve this type of question using prefix-sum algorithm, which can do this in O(n) time and space.
You can also refer to this article.
For practice on this type of questions, refer this
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论