https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted

一 题目

给定一个已按照 非递减顺序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。
函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 1 开始计数 ，所以答案数组应当满足
1 <= answer[0] < answer[1] <= numbers.length
你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。

示例 1： 输入：numbers = [2,7,11,15], target = 9 输出：[1,2] 解释：

2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。

示例 2： 输入：numbers = [2,3,4], target = 6

输出：[1,3]

示例 3： 输入：numbers = [-1,0], target = -1

输出：[1,2]

提示：

2 <= numbers.length <= 3 * 104 -1000 <= numbers[i] <= 1000 numbers 按 非递减顺序 排列 -1000 <= target <= 1000

仅存在一个有效答案

二 题解—双指针遍历

  1. class Solution {
  2.     public int[] twoSum(int[] numbers, int target) {
  3.         int length = numbers.length;
  4.         int start = 0;
  5.         int end = length - 1;
  6.         while(start<length){
  7.             while(start<end){
  8.                 if(numbers[start]+numbers[end]<target){
  9.                     start ++;
  10.                     end = length - 1;
  11.                 }
  12.                 if((numbers[start]+numbers[end])==target){
  13.                     return new int[]{start+1,end+1};
  14.                 }
  15.                 end --;
  16.             }
  17.         }
  18.         return null;
  19.     }
  20. }

三 题解—双指针二分法

  1. class Solution {
  2.     public int[] twoSum(int[] numbers, int target) {
  3.         int length = numbers.length;
  4.         int tagA = 0;
  5.         int tagB = length-1;
  6.         for(;tagA<length;tagA++){
  7.             int numA = numbers[tagA];
  8.             tagB = length -1;
  9.             int targetNum = target - numA;
  10.             tagB = binarySearch(numbers,tagA+1,tagB,targetNum);
  11.             if(tagB != -1){
  12.                 break;
  13.             }
  14.         }
  15.         return new int[]{tagA+1,tagB+1};
  16.     }
  19.     private int binarySearch(int[] nums,int start,int end,int target){
  20.         if(nums[end]<target){
  21.                 return -1;
  22.         }
  23.         while (start<=end){
  24.             int mid = start + (end - start)/2;
  25.             int midNum = nums[mid];
  26.             if(target == midNum){
  27.                 return mid;
  28.             }else if(target > midNum){
  29.                 start = mid +1;
  30.             }else {
  31.                 end = mid ;
  32.             }
  33.         }
  34.         return -1;
  35.     }
  36. }

四 同类型题目

leetcode 1 号算法题：两数之和
https://leetcode-cn.com/problems/two-sum/
leetcode 167 号算法题：两数之和Ⅱ - 输入有序数组
https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/
leetcode 170 号算法题：两数之和Ⅲ - 数据结构设计（需Plus 会员）
https://leetcode-cn.com/problems/two-sum-iii-data-structure-design/
leetcode 653 号算法题：两数之和Ⅳ - 输入 BST
https://leetcode-cn.com/problems/two-sum-iv-input-is-a-bst/
leetcode 15 号算法题：三数之和
https://leetcode-cn.com/problems/3sum/
leetcode 18 号算法题：四数之和
https://leetcode-cn.com/problems/4sum/