167. 两数之和||- 输入有序数组

题意：

解题思路：

思路：双指针
1. 使用两个指针left从左向右，right从右向左，移动之前比较target
2. 大于target则左移right--，小于则左移left++

PHP代码实现：

class Solution {
    /**
     * @param Integer[] $numbers
     * @param Integer $target
     * @return Integer[]
     */
    function twoSum($numbers, $target) {
        $map = [];
        foreach ($numbers as $k => $v) {
            $diff = $target - $v;
            if (isset($map[$diff])) return [$map[$diff] + 1, $k + 1];
            $map[$v] = $k;
        }
        return $map;
    }
    function twoSumO1($numbers, $target) {
        $left = 0;
        $right = count($numbers) - 1;
        while ($left < $right) {
            $sum = $numbers[$left] + $numbers[$right];
            if ($sum == $target) {
                return [$left + 1, $right + 1];
            } else if ($sum > $target) {
                $right--;
            } else {
                $left++;
            }
        }
        return [];
    }
}

go代码实现：

func twoSum(numbers []int, target int) []int {
    twoSumO1(numbers, target)
    l, r := 0, len(numbers) - 1
    for l < r {
        sum := numbers[l] + numbers[r]
        if sum == target {
            return []int{l + 1, r + 1}
        } else if sum > target {
            r--
        } else {
            l++
        }
    }
    return []int{}
}
func twoSumO1(numbers []int, target int) []int {
    m := map[int]int{}
    for i, v := range numbers {
        diff := target - v
        if index, key := m[diff]; key {
            return []int{index + 1, i + 1}
        }
        m[v] = i
    }
    return []int{}
}