Two Sum

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

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

Thoughts

经典的收尾双指针题目。需要先对数组排序，因此需要一个特别的数据结构存储index和值。利用的性质是如果当前nums[start] + nums[end] < target，则代表nums[start]太小，它和任何end之前的元素（也就是当前数组所有元素）也不可能成为target, 把start++，即刨除start元素；>target时同理, end不可能和任何坐标大于start的元素组成target, end--, 刨除当前end。

本质上l,r是尽量往接近target值的方向，但不一定移动后就一定比上次更接近，比如[1,4,5], taget是7，现在首尾加起来是6, 2sum保证r不会往后移动，但无法保证往前移就一定更close，比如当前往前移就变成了9。因此找close时要记录下全局最close的值。

Code

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        int[] res = new int[2];
        while (l < r) {
            int sum = nums[l] + nums[r];
            if (sum == target) {
                res[0] = l + 1;
                res[1] = r + 1;
                return res;
            } else if (sum < target) {
                l++;
            } else {
                r--;
            }
        }

        return res;
    }
}

Analysis

时间复杂度O(n). 空间O(1).