(9)Go对撞指针法求数组两数之和

方法1，暴力解法，双层遍历，时间复杂度O(n^2)
// 暴力解法,双层遍历,O(n^2)
func twoSum(numbers []int, target int) []int {
    l := len(numbers)

    for i := 0; i < l; i++ {
        for j := i + 1; j < l; j++ {
            if numbers[i]+numbers[j] == target {
                return []int{i + 1, j + 1}
            }
        }
    }
    return nil 
}

方法2：二分查找法，时间复杂度O（nlogn）
暴力解法充分利用数组的特性有序这一点，有序容易想到二分查找法
func twoSum2(numbers []int, target int) []int {
    l1 := len(numbers)
    l2 := l1

    for i := 0; i < l1; i++ {
        v := target - numbers[i]
        for j := i + 1; j < l2; {
            mid := j + (l2-j)/2
            if v == numbers[mid] {
                return []int{i + 1, mid + 1}
            } else if v < numbers[mid] { // v在左边
                l2 = mid
            } else { // v在右边
                j = mid + 1
            }
        }
    }
    return nil
}

方法3：对撞指针法，时间复杂度O(n)
// 利用有序的特征，定义左右两个指针i,j,寻找nums[i]+nums[j]=target
// if nums[i]+nums[j]<target，i++；else if nums[i]+nums[j]>target，j--，并更新sum值
func twoSum3(numbers []int, target int) []int {
    i, j := 0, len(numbers)-1

    sum := numbers[i] + numbers[j]
    for sum != target {
        if sum < target {
            i++
        } else {
            j--
        }
        sum = numbers[i] + numbers[j]
    }
    return []int{i + 1, j + 1}
}

提交leetcode，通过