C++, 6ms: Two Pointers, 6ms: Binary Search, Clean Code


  • 1

    6ms: Two Pointers
    Time: O(n)
    Space: O(1)

    vector<int> twoSum(vector<int>& numbers, int target) {
        int low = 0;
        int high = numbers.size() - 1;
    
        while(low < high){
            int sum = numbers[low] + numbers[high];
    
            if(target == sum) return vector<int>({low+1, high+1});
            if(target > sum) ++low;
            else --high;
        }
        return vector<int>();
    }
    

    6ms: Binary Search
    Time: O(nlogn)
    Space: O(1)

    vector<int> twoSum(vector<int>& numbers, int target) {
        for(int i = 0; i < numbers.size(); ++i){
            int index = bs(numbers, i+1, numbers.size(), target - numbers[i]);
            
            if(index < 0) continue;
            else return vector<int>({i+1, index+1});
        }
        return vector<int>();
    }
    
    int bs(vector<int>& numbers, int low, int high, int target){
        while(low < high){
            int mid = low + (high - low) / 2;
            if(numbers[mid] == target) return mid;
            if(target > numbers[mid]) low = mid + 1;
            else high = mid - 1;
        }
        return numbers[low] == target ? low : -1;
    }
    

Log in to reply
 

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