Tuesday, August 14, 2012

How to Solve 3-Sum Problem

Given a set S of n integers, are there elements a, b, c in S such that a + b + c = 0?
package main

import (
    "fmt"
    "sort"
)

func ThreeSum(numbers []int) {
    for i := 0; i < len(numbers); i++ {
        for j := 0; j < len(numbers); j++ {
            nSearch := -(numbers[i] + numbers[j])
            index := sort.SearchInts(numbers, nSearch)
            if index < len(numbers) && numbers[index] == nSearch {
                fmt.Println(numbers[i], numbers[j], numbers[index])
            }
        }
    }
}

func main() {
    numbers := []int{-40, 30, -10, 50, 20}
    sortedNumbers := sort.IntSlice(numbers)
    sort.Sort(sortedNumbers)
    ThreeSum(sortedNumbers)
}

No comments:

Post a Comment