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

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

url

题目

给定一个已按照 升序排列  的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。

函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 1 开始计数 ，所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。

输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
输入：numbers = [2,3,4], target = 6
输出：[1,3]
输入：numbers = [-1,0], target = -1
输出：[1,2]

方法

题目说已排序，因此双指针即可解决

• 一个在起点位置，一个在末尾位置。

code

js

let twoSum = (numbers, target) => {
    if (numbers === null) return null;
    // 双指针
    let p1 = 0, p2 = numbers.length - 1;
    while (p1 < p2) {
        let sum = numbers[p1] + numbers[p2];
        if (sum === target)
            return [p1 + 1, p2 + 1];
        else if (sum < target)
            p1++;
        else
            p2--;
    }
    return [];
}
// console.log(twoSum([2, 7, 11, 15], 9));
console.log("Hello World!");

go

func twoSum1(numbers []int, target int) []int {
	if numbers == nil || len(numbers) == 0 {
		return nil
	}
	p1, p2 := 0, len(numbers) - 1
	for p1 < p2 {
		sum := numbers[p1] + numbers[p2]
		if sum == target {
			return []int{p1 + 1, p2 + 1}
		} else if sum < target {
			p1++
		} else {
			p2--
		}
	}
	return nil
}

java

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        if (numbers == null) return null;
        // 双指针
        int p1 = 0, p2 = numbers.length - 1;
        while (p1 < p2) {
            int sum = numbers[p1] + numbers[p2];
            if (sum == target) return new int[]{p1+1, p2+1};
            else if (sum < target) p1++;
            else p2--;
        }
        
        return null;
    }
}