题目描述

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 and you may not use the same element twice.

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

解法一

思路

这题是典型的可以用双指针算法做的题。初始时头指针指向数组的第一个元素,尾指针指向数组的最后一个元素;如果当前的和等于target,那么直接返回指针;如果当前的和小于target,那么将头指针向后移动一位(这样和会增大);如果当前的和大于target,那么将尾指针向前移动一位(这样和会减小)。

这个算法并没有遍历到所有的组合情况,那么这个算法正确吗?实际上可以把这个算法理解为遍历到了所有的情况,只是将某些不可能的情况直接跳过了,比如当当前的和小于target时,【头指针之前的元素】不可能与尾指针元素的和等于target(因为头指针之前的元素都会比头指针元素小)。

Python

class Solution(object):
    def twoSum(self, numbers, target):
        """
        :type numbers: List[int]
        :type target: int
        :rtype: List[int]
        """
        i = 0
        j = len(numbers) - 1
        while i < j:
            two_sum = numbers[i] + numbers[j]
            if two_sum == target:
                break
            if two_sum > target:
                j -= 1
            else:
                i += 1
        return [i + 1, j + 1]

Java

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int i = 0;
        int j = numbers.length - 1;
        while (i < j) {
            int twoSum = numbers[i] + numbers[j];
            if (twoSum == target) {
                break;
            }
            if (twoSum > target) {
                j--;
            } else {
                i++;
            }
        }
        return new int[] {i + 1, j + 1};
    }
}

C++

class Solution {
public:
    vector<int> twoSum(vector<int> &numbers, int target) {
        int i = 0;
        int j = numbers.size() - 1;
        while (i < j) {
            int twoSum = numbers[i] + numbers[j];
            if (twoSum == target) {
                break;
            }
            if (twoSum > target) {
                j--;
            } else {
                i++;
            }
        }

        return vector<int> {i + 1, j + 1};
    }
};