1. Two Sum

Description

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Answer

Bruce Force

package main

import "fmt"

func twoSum(nums []int, target int) []int {
    var sum, i, j int
    arr := make([]int, 2, 2)
    for i = 0; i < len(nums); i++ {
        for j = i + 1; j < len(nums); j++ {
            if i != j  {
                sum = nums[i] + nums[j]
                if sum == target {
                    arr[0] = i
                    arr[1] = j
                }
            }
        }
    }

    return arr
}

func main() {
    a := []int{2, 7, 11, 15}

    fmt.Println(twoSum(a, 9))
}

总结

这个解法是暴力求解，时间复杂度是O（n2）,空间复杂度是O（1）

approach2 利用map的特性

Time complexity：O（n）
Space complexity:O(n)

//利用map的特性，降低时间复杂度
func twoSum2(nums []int, target int) []int {

    arr := make([]int, 2, 2)

    hashmap := make(map[int]int)
    for i := 0; i < len(nums); i++ {
        hashmap[nums[i]] = i
    }
    var complement int
    for i := 0; i < len(nums); i++ {
        complement = target - nums[i]
        value, ok := hashmap[complement]
        if ok == true {
            if value != i {
                arr[0] = i
                arr[1] = value
                break
            }

        }

    }
    return arr

}