Tow Sum

题目描述

给定一个已按非递减顺序排列的整数数组 numbers(下标从 1 开始), 找出两个不同的数使得它们的和等于给定的目标数 target. 这两个数需满足 1 <= index1 < index2 <= numbers.length, 并以数组形式返回它们的下标 [index1, index2](下标从 1 开始).

题目保证存在且仅存在一个解.

输入格式

第一行包含一个整数 numbers.length.

第二行包含若干个由空格分隔的整数, 表示数组 numbers. 数组的长度范围在 [2, 3*10^4] 之间, 且保证按非递减顺序排列.

第三行包含一个整数 target, 表示目标数.

输出格式

输出两个整数, 以空格分隔, 表示满足条件的两个下标, 且 index1 < index2.

样例

样例输入

4
2 7 11 15
9

样例输出

1 2

样例解释

numbers[1] + numbers[2] = 2 + 7 = 9, 因此返回 [1, 2].

说明

• -2 * 10^5 <= target <= 2 * 10^5.
• numbers.length <= 160000.
• 题目数据保证有且仅有一个有效解.

提示

• 双指针
• 二分查找