leetcode top100

1.求两数之和（数组无序）

//方法一：暴力破解 时间o(n^2) 空间o(1)
func TwoNumSum1(nums []int, target int) []int {
    for i := 0; i < len(nums)-1; i++ {
        for j := i + 1; j < len(nums); j++ {
            if nums[i]+nums[j] == target {
                return []int{i, j}
            }
        }
    }
    return nil
}

//方法二：空间换时间 时间o(n)  空间o(n)
func TwoNumSum2(nums []int, target int) []int {
    result := make([]int, 0)
    realIndex := make(map[int]int)
    for i, v := range nums {
        if valueIndex, ok := realIndex[target-v]; ok {
            return append(result, valueIndex, i)
        } else {
            realIndex[v] = i
        }
    }
    return result
}

2.求电话号码的字母组合

func letterCombinations(digits string) []string {
    m:=make(map[byte][]string)
    m['2']=[]string{"a","b","c"}
    m['3']=[]string{"d","e","f"}
    m['4']=[]string{"g","h","i"}
    m['5']=[]string{"j","k","l"}
    m['6']=[]string{"m","n","o"}
    m['7']=[]string{"p","q","r","s"}
    m['8']=[]string{"t","u","v"}
    m['9']=[]string{"w","x","y","z"}
    var ret []string
    for i:=0;i<len(digits);i++{
        ret=getCombination(ret,m[digits[i]])
    }
    return ret
}
func getCombination(a,b []string)[]string{
    if len(a)==0{
        return b
    }
    if len(b)==0{
        return a
    }
    var ret []string 
    for _,v:=range a{
        for _,bv:=range b {
            ret=append(ret,v+bv)
        }
    }
    return ret
}

3.三数之和

func ThreeNumsTwo(nums []int) [][]int {
    if len(nums) < 3 {
        return nil
    }
    sort.Ints(nums)
    fmt.Println(nums)
    flag := false
    for _, v := range nums {
        if v != 0 {
            flag = true
        }
    }
    //全0的情况
    if !flag {
        return [][]int{{0, 0, 0}}
    }
    result := make([][]int, 0)
    L := 0
    R := len(nums) - 1
    for i, v := range nums {
        //当前这个元素都大于0了，后面的元素加起来不可能等于0
        if nums[i] > 0 {
            return result
        }
        // 去除重复的元素排序后相邻
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }
        //每次进入重置指针
        L = i + 1
        R = len(nums) - 1
        for L < R {
            if 0 == nums[L]+nums[R]+v {
                result = append(result, []int{v, nums[L], nums[R]})
                //第二个元素重复的情况
                for L < R && nums[L] == nums[L+1] {
                    L++
                }
                //第三个元素重复的情况
                for L < R && nums[R] == nums[R-1] {
                    R--
                }
                L++
                R--
            } else if nums[L]+nums[R]+v < 0 {
                L++
            } else {
                R--
            }
        }

    }
    return result
}

4.两数之和（链表）

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    if l1 == nil {
        return l2
    }
    if l2 == nil {
        return l1
    }
    head := &ListNode{
        Val: 0,
    }
    curr := head
    nextAdd := 0
    for l1 != nil || l2 != nil {
        x, y := 0, 0
        if l1 != nil {
            x = l1.Val
        }
        if l2 != nil {
            y = l2.Val
        }
        sum := x + y + nextAdd
        if nextAdd > 0 {
            nextAdd = 0
        }
        val := sum % 10
        nextAdd = sum / 10
        node := &ListNode{
            Val: val,
        }
        if l1 != nil {
            l1 = l1.Next
        }
        if l2 != nil {
            l2 = l2.Next
        }
        curr.Next = node
        curr = node
    }
    if nextAdd != 0 {
        node := &ListNode{
            Val: nextAdd,
        }
        curr.Next = node
        curr = node
    }
    return head.Next
}