连接时的长度L，当N条(1≤N≤5000)条的长度由标准输入提供时，是通过连接N条条中的三个长度得到的L请写一个程序找出组合的总数。但是，和单个柱子的长度一样，拼凑出来的长度(L)是一个正整数，在32bit整数范围内足够处理。此外，它具有所有长度不同的栏。

例如) 输入:

15
5
8
4
10
3
2

输出:

2 //{{2, 3, 10}, {3, 4, 8}}

示例 2) 输入:

35
10
13
12
17
10
4
18
3
11
5
7

输出:

6 //{{4, 13, 18}, {5, 12, 18}, {5, 13, 17}, {7, 10, 18}, {7, 11, 17}, {10, 12, 13}}

我的答案在这里

package main

import (
    "fmt"
    "sort"
)

func main() {
    input_count := 0
    var target int
    var count int
    var v int
    var array []int
    for read_count, _ := fmt.Scan(&v); read_count != 0; read_count, _ = fmt.Scan(&v) {
        if 0 == input_count {
            target = v
        } else if 1 == input_count {
            count = v
            array = make([]int, count)
        } else {
            array[input_count-2] = v
        }
        input_count++
    }
    sort.Ints(array)
    fmt.Println(Calculate(target, count, array))
}

func Except(pair []int, count int, array []int) []int {
    except := make([]int, count-pair[2])
    except_index := 0
    on := false
    for _, v := range array {
        if on {
            except[except_index] = v
            except_index++
        }
        if v == pair[1] {
            on = true
        }

    }
    return except
}

func ListUp(target int, count int, array []int) [][]int {
    max := array[count-1]
    list := make([][]int, Fact(count-1))
    list_index := 0
    for i, h := range array {
        if count > i+1 && target > h+array[i+1] {
            for j, v := range array[i+1:] {
                if count > i+j+1 && target <= max+h+v && target > h+v {
                    list[list_index] = []int{h, v, i + j + 1}
                    list_index++
                }
            }
        }
    }
    return list
}

//func Calculate(target int, count int, array []int) [][]int {
func Calculate(target int, count int, array []int) int {
    //  var answers [][]int
    answer_count := 0
    for _, pair := range ListUp(target, count, array) {
        if 3 == len(pair) {
            pair_sum := pair[0] + pair[1]
            if target-pair_sum >= array[0] {
                for _, v := range Except(pair, count, array) {
                    if target == pair[0]+pair[1]+v {
                        //                      answers = append(answers, []int{pair[0], pair[1], v})
                        answer_count++

                    }
                }
            }
        }
    }
    return answer_count
}

func Fact(n int) int {
    if n == 0 {
        return 0
    }
    return n + Fact(n-1)
}

有人可以重构代码吗？ 你应该重构它 如果输入 https://github.com/freddiefujiwara/horiemon-challenge-codeiq/blob/master/sample4.txt 然后输出

1571200

10 秒内

当前状态在这里

time ./horiemon-challenge-codeiq < sample4.txt
1571200

real    6m56.584s
user    6m56.132s
sys     0m1.578s

非常非常慢。

最佳答案

你将近七分钟的时间非常非常慢。十秒很慢。一秒比较合理，十分之一秒就好。例如，使用 O(N*N) 算法，

package main

import (
    "bufio"
    "errors"
    "fmt"
    "io"
    "os"
    "sort"
    "strconv"
    "strings"
)

func triples(l int, b []int) int {
    t := 0
    sort.Ints(b)
    // for i < j < k, b[i] <= b[j] <= b[k]
    for i := 0; i < len(b)-2; i++ {
        x := b[i]
        if x > l {
            break
        }
        lx := l - x
        j, k := i+1, len(b)-1
        y := b[j]
        z := b[k]
        for j < k {
            yz := y + z
            switch {
            case lx > yz:
                j++
                y = b[j]
            case lx < yz:
                k--
                z = b[k]
            default:
                // l == b[i]+b[j]+b[k]
                t++
                j++
                k--
                y = b[j]
                z = b[k]
            }
        }
    }
    return t
}

func readInput() (l int, b []int, err error) {
    r := bufio.NewReader(os.Stdin)
    for {
        line, err := r.ReadString('\n')
        line = strings.TrimSpace(line)
        if err == nil && len(line) == 0 {
            err = io.EOF
        }
        if err != nil {
            if err == io.EOF {
                break
            }
            return 0, nil, err
        }
        i, err := strconv.Atoi(string(line))
        if err == nil && i < 0 {
            err = errors.New("Nonpositive number: " + line)
        }
        if err != nil {
            return 0, nil, err
        }
        b = append(b, i)
    }

    if len(b) > 0 {
        l = b[0]
        b = b[1:]
        if len(b) > 1 {
            n := b[0]
            b = b[1:]
            if n != len(b) {
                err := errors.New("Invalid number of bars: " + strconv.Itoa(len(b)))
                return 0, nil, err
            }
        }
    }
    return l, b, nil
}

func main() {
    l, b, err := readInput()
    if err != nil {
        fmt.Fprintln(os.Stderr, err)
        return
    }
    t := triples(l, b)
    fmt.Println(t)
}

输出:

1571200
real    0m0.164s
user    0m0.161s
sys     0m0.004s

为了比较，你的程序，

输出:

1571200
real    9m24.384s
user    16m14.592s
sys     0m19.129s

关于go - 在数组中找到 3 对的挑战，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/30962088/