# 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).


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hao-fu-1.gitbook.io/oj/multiple-pointers/two_sum.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.