A simple O(n) solution


  • 43
    A

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

    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});
    }
    

    };


  • 0
    A

    @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
    X

    Because it is said not 0 indexed.


  • 2
    J

    @allbugs

    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
    C

    @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?


Log in to reply
 

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