167. Two Sum II - Input array is sorted

  • 47.6%

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.

1
2
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

方法一:

双指针,不断收缩查找范围,来找到响应元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int lo=0, hi=numbers.size()-1;
while(numbers[lo]+numbers[hi] != target){
if(numbers[lo]+numbers[hi]<target)
lo++;
else
hi--;
}
return vector<int>({lo+1, hi+1});
}
};

我的代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
vector<int> res;
int left = 0, right = numbers.size()-1;
while(left<right){
int sum = numbers[left] + numbers[right];
if(sum==target){
res.push_back(left+1);
res.push_back(right+1);
return res;
}else if(sum>target)
right--;
else
left++;
}
}
};

6ms, September 11, 2016

https://discuss.leetcode.com/topic/12660/a-simple-o-n-solution

A simple O(n) solution

We only have to shrink the range to find the pair:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int lo=0, hi=numbers.size()-1;
while(numbers[lo]+numbers[hi] != target){
if(numbers[lo]+numbers[hi]<target)
lo++;
else
hi--;
}
return vector<int>({lo+1, hi+1});
}
};

https://discuss.leetcode.com/topic/7465/a-less-efficient-way-binary-search

A less efficient way (binary search)

I know that the best solution is using two pointers like what is done in the previous solution sharing. However, I see the tag contains “binary search”. I do not know if I misunderstand but is binary search a less efficient way for this problem.

Say, fix the first element A[0] and do binary search on the remaining n-1 elements. If cannot find any element which equals target-A[0], Try A[1]. That is, fix A[1] and do binary search on A[2] ~ A[n-1]. Continue this process until we have the last two elements A[n-2] and A[n-1] .

Does this gives a time complexity lg(n-1) + lg(n-2) + … + lg(1) ~ O(lg(n!)) ~ O(nlgn). So it is less efficient than the O(n) solution. Am I missing something here?

The code also passes OJ.

1
2
3
4
5
6
7
8
9
10
11
12
vector<int> twoSum(vector<int> &numbers, int target) {
if(numbers.empty()) return {};
for(int i=0; i<numbers.size()-1; i++) {
int start=i+1, end=numbers.size()-1, gap=target-numbers[i];
while(start <= end) {
int m = start+(end-start)/2;
if(numbers[m] == gap) return {i+1,m+1};
else if(numbers[m] > gap) end=m-1;
else start=m+1;
}
}
}

https://discuss.leetcode.com/topic/7465/a-less-efficient-way-binary-search/6

My idea is to use binary search to find the largest number less than target and then use two pointers.


https://discuss.leetcode.com/topic/32373/c-solution-simple-and-sweet

C++ solution simple and sweet

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<int> twoSum(vector<int>& numbers, int target) {

int l = 0;
int r = numbers.size() -1;
while(l < r){
if(numbers[l] + numbers[r] == target){
vector<int> res{l+1,r+1};
return res;
}
else if(numbers[l] + numbers[r] > target){
r--;
}
else{
l++;
}
}
}

https://discuss.leetcode.com/topic/21800/python-different-solutions-two-pointer-dictionary-binary-search

Python different solutions (two-pointer, dictionary, binary search).

1
2
3
4
5
6
7
8
9
10
11
# two-pointer
def twoSum1(self, numbers, target):
l, r = 0, len(numbers)-1
while l < r:
s = numbers[l] + numbers[r]
if s == target:
return [l+1, r+1]
elif s < target:
l += 1
else:
r -= 1
1
2
3
4
5
6
7
# dictionary           
def twoSum2(self, numbers, target):
dic = {}
for i, num in enumerate(numbers):
if target-num in dic:
return [dic[target-num]+1, i+1]
dic[num] = i
1
2
3
4
5
6
7
8
9
10
11
12
13
# binary search        
def twoSum(self, numbers, target):
for i in xrange(len(numbers)):
l, r = i+1, len(numbers)-1
tmp = target - numbers[i]
while l <= r:
mid = l + (r-l)//2
if numbers[mid] == tmp:
return [i+1, mid+1]
elif numbers[mid] < tmp:
l = mid+1
else:
r = mid-1

my code

38ms, 89.75%, Dec.1st, 2016

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
def twoSum(self, numbers, target):
"""
:type numbers: List[int]
:type target: int
:rtype: List[int]
"""
if len(numbers) < 2: return []
i, j = 0, len(numbers)-1
while i < j:
if numbers[i] + numbers[j] > target:
j -= 1
elif numbers[i] + numbers[j] < target:
i += 1
else:
return [i+1, j+1]


1ms, September 11, 2016

https://discuss.leetcode.com/topic/39962/java-7-line-simple-solution

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
public int[] twoSum(int[] numbers, int target) {
int start = 0, end = numbers.length - 1;
while(start < end){
if(numbers[start] + numbers[end] == target) break;
if(numbers[start] + numbers[end] < target) start++;
else end--;
}
return new int[]{start+1, end+1};
}
}
谢谢你,可爱的朋友。