Java 1ms with two pointers


  • 0
    T

    1ms. Two pointers.

    1. Set head and tail to proper positions.
    2. Begin search.
    public int[] twoSum(int[] numbers, int target) {
            if(numbers == null) throw new IllegalArgumentException("Invalid Input");
            
            int head = 0;
            int minReq = target - numbers[numbers.length-1];
            while(numbers[head] < minReq)
            	head++;
            
            int tail = numbers.length-1;
            int maxReq = target - numbers[0];
            while(numbers[tail] > maxReq)
            	tail--;
            
            while(head < tail)
            {
            	if(numbers[head] + numbers[tail] == target) return new int[]{head+1, tail+1};
            	else if(numbers[head]+numbers[tail] < target) head++;
            	else tail--;
            }
            return new int[0];
        }
    

  • 0
    D
    This post is deleted!

  • 0
    D

    if size of numbers is big ,the run time should lager than Binary Search。


Log in to reply
 

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