167.md

167. Two Sum II - Input Array Is Sorted

Leetcode link

解题思路

题目要求我们从一个排序好的数组中找出唯一的两个元素使得相加为 target

因为数组是排序好的，且答案有唯一性，我们可以考虑用双指针来求解

具体来说，我们可以用两个指针 left 与 right 分别指向数组的开头与结尾

• 当两个指针所指元素之和小于 target，则 left++
• 当两个指针所指元素之和大于 target，则 right--
• 如果两个指针元素之和等于 target，直接返回 [left + 1, right + 1]

C++

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

Javascript

var twoSum = function(numbers, target) {
    let left = 0,
        right = numbers.length - 1;
    
    while(left < right) {
        let sum = numbers[left] + numbers[right];
        if(sum === target) {
            return [left+1, right+1];
        } else if(sum > target) {
            right--;
        } else if(sum < target) {
            left++;
        }
    }
};