• 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.

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:

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.

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

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

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

my code

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

1ms, September 11, 2016

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