Java 0ms with two pointers and binary search


  • 0
    J
    public class Solution {
        public int[] twoSum(int[] numbers, int target) {
            if (numbers.length <= 1) {
                return new int[]{0, 0};
            }
    
            int start = 0;
            int end = numbers.length - 1;
            while (start < end) {
                int value = numbers[start] + numbers[end];
                if (value == target) {
                    return new int[]{start + 1, end + 1};
                } else if (value < target) {
                    start = binarySearch(numbers, start + 1, end - 1, target - numbers[end]);
                } else {
                    end = binarySearch(numbers, start + 1, end - 1, target - numbers[start]);
                }
            }
            throw new RuntimeException("not found!");
        }
    
        private int binarySearch(int[] nums, int start, int end, int target) {
            while (start < end) {
                int mid = start + (end - start) / 2;
                if (nums[mid] == target) {
                    return mid;
                } else if (nums[mid] < target) {
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            }
            return start;
        }
    }
    

  • 0
    X

    @jonsnow1984 the worst case is O(n log n) ?


  • 0
    X

    @xiaowu4 It isn't O(n log n), can you tell me the time complexity.


  • 0
    J

    @xiaowu4 Should be O(log n).
    It looks like O(n log n) at first glance. But since we are updating the "start" and "end" inside the loop with the binary search way, it's actually O(log n).


  • 0
    A

    @jonsnow1984 Could you explain the difference between returning start and returning end in your binarySearch function? Can't seem to wrap my head around it.


Log in to reply
 

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