java 1ms solution using two pointers with explanation


  • 1
    F

    First, come with the ac code:

        public int[] twoSum(int[] numbers, int target) {
            int low = 0, high = numbers.length - 1;
            while (low < high) {
                long tmp = numbers[low] + numbers[high];
                if (tmp == target) {
                    return new int[]{low + 1, high + 1};
                } else if (tmp < target) {
                    low++;
                } else {
                    high--;
                }
            }
            return null;
        }
    

    The key point is how we utilize the properties of the input array which is sorted in ascending order. We use two pointers: low and high to scan the array.
    Once at a time, if tmp is less than target, there are two cases:

    • maintain numbers[low], and find another value greater than numbers[high], so that the sum of the two values can reach target
    • maintain numbers[high], and find another value greater than numbers[low], so that the sum of the two values can reach target
      obviously, the first case is impossible, because numbers[high] is already the largest number in the array, so only the second case is possible, we find another value greater than numbers[low] by simply increase low, which refers to low++.

    Similarly, if tmp is greater than target, there are two cases:

    • maintain numbers[low], and find another value less than numbers[high], so that the sum of the two values can reach target
    • maintain numbers[high], and find another value less than numbers[low], so that the sum of the two values can reach target
      obviously, the second case is impossible, because numbers[low] is already the smallest number in the array, so only the first case is possible, we find another value smaller than numbers[low] by simply decrease high, which refers to high--.

Log in to reply
 

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