A simple O(n) solution

  • 47

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

    class Solution {


    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){
            } else {
        return vector<int>({lo+1,hi+1});


  • 0

    @allbugs Why do we increment the value of the index by 1 before adding it to the vector? Why is it lo + 1? and not lo?

  • 3

    Because it is said not 0 indexed.

  • 3


    so many issues with your code.

    1. lo may greater than numbers.size()-1 and hi may be smaller than 0
    2. what will happen if there is no answer
    3. could you do numbers[lo]+numbers[hi] just once?

  • 0

    @allbugs I had written a similar code but when I try to submit , For large input it throws time limit exceeded. Any suggestions ? Were you able to submit?

  • 0

    @jh2016 I think it's mentioned that "You may assume that each input would have exactly one solution", meaning there will always be a solution, so no need to worry about your concerns?

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.