在阵列中找到3对的挑战

Question

The length L at the time of joining, when the length of the bar of the N (1 ≦ N ≦ 5000) is supplied from standard input, is the L by connecting three lengths among the N number of bars please write a program to find the total number of combinations of. However, and the length of the individual bars, length was pieced together (L) is a positive integer, is sufficient handle range in 32bit integer. In addition, it has all the length of the bar different things.

for example) input:

15
5
8
4
10
3
2

output:

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

example 2) input :

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

output:

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

and my answer is here

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)
}

Does anyone who can refactor the code? and you should refactor it if input https://github.com/freddiefujiwara/horiemon-challenge-codeiq/blob/master/sample4.txt then output

1571200

in 10 seconds

current status is here

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

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

very very slow.

Answer 1

Your time of almost seven minutes is very, very slow. Ten seconds is slow. One second is more reasonable, a tenth of a second is good. For example, using an O(N*N) algorithm,

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('
')
        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)
}

Output:

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

For comparison, your program,

Output:

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