//暴力 1. 两数之和
时间复杂度o(n*n)

func twoSum(nums []int, target int) []int {
    a := []int{0, 0}
    for i := 0; i < len(nums); i++ {
        for j := i + 1; j < len(nums); j++ {
            if nums[i]+nums[j] == target {
                a[0], a[1] = i, j
                return a
            }
        }
    }
    return a
}

//二分(无序不用二分) 167. 两数之和 II - 输入有序数组

func twoSum(numbers []int, target int) []int {
    lens := len(numbers)
    for i := 0; i < lens; i++ {
        x := numbers[i]
        y := (i + lens) / 2
        //fmt.Println(i, (i + lens/2))
        if x+numbers[y] > target {
            for j := y; j >= i+1 && j < lens; {
                if x+numbers[j] == target {
                    return []int{i + 1, j + 1}
                }
                j--

            }
        } else if x+numbers[y] < target {
            for j := y; j >= i+1 && j < lens; {
                if x+numbers[j] == target {
                    return []int{i + 1, j + 1}
                }
                j++

            }
        } else {
            return []int{i + 1, y + 1}
        }

    }
    return []int{}
}

//hashmap 167. 两数之和 II - 输入有序数组

func twoSum(numbers []int, target int) []int {
    map1 := make(map[int]int)
    for a, b := range numbers {
        if i, ok := map1[target-b]; ok {
            return []int{a, i}
        }
        map1[b] = a
    }
    return []int{}
}

//双指针(有序数组) 167. 两数之和 II - 输入有序数组

func twoSum(numbers []int, target int) []int {
    i, j := 0, len(numbers)-1
    for i < j {
        if numbers[i]+numbers[j] == target {
            return []int{i + 1, j + 1}
        } else if numbers[i]+numbers[j] > target {
            j--
        } else {
            i++
        }
    }
    return []int{}
}