LeetCode刷题实战167：两数之和 II - 输入有序数组-轻识

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 两数之和 II - 输入有序数组 ，我们先来看题面：

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

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.

Note:

Your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution and you may not use the same element twice.

题意

给定一个已按照升序排列的有序数组，找到两个数使得它们相加之和等于目标数。

函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。

说明:

返回的下标值（index1 和 index2）不是从零开始的。

你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。

样例

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

解题

https://blog.csdn.net/weixin_41943637/article/details/103343131

思路1:双层循环

class Solution {
    public int[] twoSum(int[] numbers, int target) {
       for (int i = 0; i < numbers.length; i++) {
            int Num = target - numbers[i];
            for (int j = i + 1; j < numbers.length; j++) {
                if (Num == numbers[j]){
                    int nums[] = {i+1,j+1};
                    return nums;
                }
            }
        }
        return null;
    }
}

思路2:双指针

前后双指针分别指向数组的首尾，如果首尾元素相加大于目标，则尾指针向前一位；反之，如果首尾元素相加小于目标，则首指针向后一位。最差情况下，整个数组也只会遍历一遍，所以时间复杂度为O(N)。

class Solution { 
   public int[] twoSum(int[] numbers, int target) { 
      int left=0; 
      int right=numbers.length-1; 
      while(left         int sum=numbers[left]+numbers[right];
         if(sum==target)return new int[]{left+1,right+1}; 
         else if(sum         else if(sum>target)right--; 
      } 
    return null; 
    }
}

思路3:二分查找

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        for(int i = 0; i < numbers.length; i++) {
            int index = binarySearchIndex(numbers, i + 1, target - numbers[i]);
            if(index != -1) {
               return new int[]{i + 1, index + 1}; 
            }
        }
        return new int[]{};
    }
    public int binarySearchIndex(int[] numbers, int startIndex, int target) {
        int low = startIndex;
        int high = numbers.length - 1;
        while(low <= high) {
            int mid = (low + high) >>> 1; 
            if(target > numbers[mid]) {
                low = mid + 1;
            } else if(target < numbers[mid]) {
                high = mid - 1;
            } else {
                return mid;
            }
        }
        return -1; 
    }
}