A O(logN) solution with easy understanding explaination


  • -1
    K

    There is a normal way to find answer like this:

    public int[] TwoSum(int[] numbers, int target)
    {
        int low = 0;
        int up = numbers.Count() - 1;
        int sum;
        while (low < up)
        {
            sum = numbers[low] + numbers[up];
            if (sum > target)
                up--;
            else if (sum < target)
                low++;
            else
                break;
        }
        return new int[] { low + 1, up + 1 };
    }
    

    This is O(N) solution.
    If the final value of low is very close to 0 and the final value of up is very close to N-1, it will work very fast.
    But if not , it will wast a lot of time to up-- and low++.
    Because the array is already sorted, we can use binary search to speed up this process.
    If sum > target, we find next up which makes numbers[low]+numbers[up-1]<target<=numbers[low]+numbers[up].
    If sum < target, we find next low which makes numbers[low]+numbers[up]<=target<numbers[low+1]+numbers[up].
    If sum = target, we get the answer.
    Here is my code:

    static int[] TwoSum(int[] numbers, int target)
    {
        int low = 0;
        int up = numbers.Count() - 1;
        int sum;
        while (low < up)
        {
            sum = numbers[low] + numbers[up];
            if (sum > target)
            {
                up = Array.BinarySearch(numbers, low, up - low + 1, target - numbers[low]);
                if (up < 0) up = ~up;
                if (numbers[low] + numbers[up] != target) up--;
            }
            else if (sum < target)
            {
                low = Array.BinarySearch(numbers, low, up - low + 1, target - numbers[up]);
                if (low < 0) low = ~low;
            }
            else
                break;
        }
        return new int[] { low + 1, up + 1 };
    }
    

    By the way, Array.BinarySearch is a method of Array class in .Net, you can find help at: https://msdn.microsoft.com/en-us/library/windows/apps/y15ef976(v=vs.105).aspx


Log in to reply
 

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