# Two Sum Input Array Is Sorted Problem

## Description

LeetCode Problem 167. Given an array of integers **nums** sorted in ascending order, and an integer **target**, return indices of the two numbers such that they add up to target.

Example:

1
2
3

Input: nums = [2,7,11,15], target = 9.
Output: [0,1].
Explanation: As nums[0] + nums[1] = 2 + 7 = 9, we return [0, 1].

## Solution

This problem is similar to the `two sum problem`

, the `three sum problem`

, and the `two sum less than k problem`

.

#### Brute Force Approach

A simple solution is to use the `brute force`

approach.

We loop through each element *x* in the array. For each element,
we loop through each of the rest elements *x’* to see whether (*x* + *x’* = *k*).

The time complexity of this approach is O(n^{2}),
and the space complexity is O(1).

#### Two Pointer Approach

We can use the `two pointer`

approach similar to the `three sum problem`

.

We set two pointers *l* and *r* pointing to the first and last element of the array, respectively. If the sum of the two elements pointed by *l* and *r* is greater than *target*, that means the right element is too big (even the smallest left element cannot satisfy the requirement), then we move the right pointer one step to the left. If the sum of the two elements pointed by *l* and *r* is smaller than *target*, that means the left element is too small (even the biggest right element cannot satisfy the requirement), then we move the left pointer one step to the right. If the sum equals to *target*, we find the solution and return the pointers.

The time complexity can be reduced to O(n), and the space complexity is O(1).

## Sample C++ Code

This is a C++ implementation of the two pointer approach.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> twoSum(vector<int>& numbers, int target) {
int len = numbers.size();
if (len == 0) return {};
int l, r;
l = 0, r = len - 1;
while (l <= r) {
if (numbers[l] + numbers[r] < target) {
l ++;
} else if (numbers[l] + numbers[r] == target) {
break;
} else {
r --;
}
}
return {l, r};
}
int main() {
vector<int> nums={2,7,11,15};
int target = 9;
vector<int> ans;
ans = twoSum(nums, target);
cout << ans[0] << " " << ans[1] << endl;
}