C++ O(logn)~O(n) : An combination of binary-search and two-pointers


  • 0
    M
    class Solution {
    public:
        vector<int> twoSum(vector<int>& numbers, int target) {
            // Current Version : Time -> O(logn) ~ O(n), space -> O(1)
            int start = 0, end = numbers.size() - 1;
            while (start + 1 < end) {
                int mid = start + (end - start) / 2;
                if (numbers[mid] + numbers[start] == target) {
                    return {start+1, mid+1};
                } else if (numbers[mid] + numbers[end] == target) {
                    return {mid+1, end+1};
                } else if (numbers[mid] + numbers[start] > target) {
                    end = mid;
                } else if (numbers[mid] + numbers[end] < target) {
                    start = mid;
                } else {
                    if (numbers[start] + numbers[end] == target) {
                        return {start+1, end+1};
                    } else if (numbers[start] + numbers[end] < target) {
                        start = start + 1;
                    } else {
                        end = end - 1;
                    }
                }
            }
            return {start+1, end+1};
            
            // Expected Version: Time -> O(logn)?
    
            /* Other Version:
            1. Binary Search:
                Solution -> i from 1 -> n, binary search target - numbers[i]
                time -> O(nlogn), space -> O(1)
            2. Two Pointers:
                Solution -> start = 0, end = n - 1
                            start + end < target start++
                            start + end > target end--
                time -> O(n), space -> O(1)
            */
        }
    };
    

Log in to reply
 

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