Question

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.
Example:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.

Thinking:

  • Method 1: O(N^2)
class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int len = numbers.length;
        for(int i = 0; i < len-1; i++){
            int find = target - numbers[i];
            for(int j = i + 1; j < len; j++){
                if(numbers[j] == find){
                    return new int[]{i + 1, j + 1};
                }else if(numbers[j] > find)
                    break;
            }
        }
        return null;
    }
}
  • Method 2: O(N)
    • 因为数组本来是按序排列的，我们可以利用sum 3的方法。
      • 求出首位的和，如果小了，左边的右移。
      • 如果打了，右边的左移。
class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int[] result = new int[2];
        int low = 0, high = numbers.length - 1;
        if(numbers.length < 2) return null;
        while(low < high){
            int sum = numbers[low] + numbers[high];
            if(sum == target){
                result[0] = low + 1;
                result[1] = high + 1;
                break;
            }else if(sum > target)
                high--;
            else
                low++;
        }
        return low >= high ? null : result;
    }
}

二刷

  1. 双指针，一个指向数组头，一个指向数组尾。
  2. 如果sum小了，low指针右移，不然high指针左移。 
    class Solution {
 public int[] twoSum(int[] numbers, int target) {
     int len = numbers.length;
     int low = 0, high = len - 1;
     int sum = numbers[low] + numbers[high];
     while(sum != target){
         if(sum < target) low++;
         else high--;
         sum = numbers[low] + numbers[high];
     }
     return new int[]{low + 1, high + 1};
 }
}