## DEV Community is a community of 794,122 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Nic

Posted on • Originally published at coderscat.com on

# LeetCode: Two Sum II – Input array is sorted

Challenge Description: Two Sum II – Input array is sorted

## Approach #1: binary search

Note the input array is already sorted. So we can iterate all the elements, for each element(suppose with a value of v1), we try to find another element with the value of `target-v1`. Binary search will suitable for this task.

The overall time complexity is (O(NlogN)).

``````class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
for(int i=0 ;i<numbers.size() - 1; i++) {
int l = i + 1;
int r = numbers.size() - 1;
int t = target - numbers[i];
while(l <= r) {
int m = (l + r) / 2;
if(numbers[m] == t) {
return vector<int> { i+1, m+1 };
} else if (numbers[m] > t) {
r = m - 1;
} else {
l = m + 1;
}
}
}
return vector<int>{};
}
};

``````

## Approach #2: two-slice

The idea of two slices is similar to binary search. In this approach, we use two index, index `l` is from left to right, index `r` is from right to left.

In each iteration, we compare the current sum of two elements with the target. There are tree cases:

1. sum == target , then we need return current two indexes.
2. sum > target , then we need to decrease index `r` .
3. sum < target , then we need to increase index `l`.

The time complexity is (O(N)).

``````class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int l = 0;
int r = numbers.size()-1;
while(l < r) {
int s = numbers[l] + numbers[r];
if(s == target) return vector<int> {l+1, r+1};
if(s > target) r--;
if(s < target) l++;
}
return vector<int>{};
}
};

``````

The post LeetCode: Two Sum II – Input array is sorted appeared first on CodersCat.