- 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 | Input: numbers={2, 7, 11, 15}, target=9 |

方法一：

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

1 | class Solution { |

我的代码实现：

1 | class Solution { |

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 | class Solution { |

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 | vector<int> twoSum(vector<int> &numbers, int target) { |

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 | vector<int> twoSum(vector<int>& numbers, int target) { |

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

1 | # two-pointer |

1 | # dictionary |

1 | # binary search |

my code

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

1 | class Solution(object): |

1ms, September 11, 2016

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

1 | public class Solution { |