leetcode [#167]

目录

• 1. 题目
• 2. 解决方案
• 3. 注意事项

题目

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. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Example:
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

---

解决方案

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int N = numbers.length;
        if(numbers == null || N == 0) return numbers;
        int[] result = new int[2];
        int last = N-1;
        for(int i = N-1; i > 0; i--){
            if(numbers[i] < target){
                last = i;
                break;
            }
        }
        int begin = 0;
        int end = N - 1;
        while(begin < end){
            if(numbers[begin] + numbers[end] == target){
                result[0] = begin+1;
                result[1] = end+1;
                break;
            } else if(numbers[begin] + numbers[end] < target){
                begin++;
            } else {
                end--;
            }
        }
        return result;
    }
}

---

注意事项

1. 以下是暴力解法，会超时：

   public class Solution {
       public int[] twoSum(int[] numbers, int target) {
           int N = numbers.length;
           if(numbers == null || N == 0) return numbers;
           int[] result = new int[2];
           for(int i = 0; i < N; i++){
               for(int j = i+1; j < N; j++){
                   if(numbers[i] + numbers[j] == target){
                       result[0] = i+1;
                       result[1] = j+1;
                   }
               }
           }
           return result;
       }
   }

2. 解决方案中，首先排除了那些大于target的元素值。对于剩下的所有元素，分别将两端的值相加，如果等于target，则返回下标即可；如果大于target，说明右端点应换做较小的值，即end--;;如果小于target，说明左端点应换做较大的值，即begin++;。