O(n) time O(1) space two pointer solution with detailed and clear explanation


  • 2

    To find the two numbers that sum to a target value, let's say the left number is numbers[i], and the right number is numbers[j].

    Let's iterate 0 to numbers.length - 1 one by one to find the left index i.

    Firstly look at when i = 0. Let's say the right j is j* satisfying numbers[i] + numbers[j*] == target. How to find j*? Let's just take a random j satisfying 0 < j < numbers.length. There are 3 situations:

    1. numbers[i] + numbers[j] == target
    2. numbers[i] + numbers[j] < target
    3. numbers[i] + numbers[j] > target

    Answer is found in situation 1.

    In situation 2, if numbers[i] + numbers[j] < target, because the array is sorted, we know that numbers[j*] > numbers[j], and j* > j. So we should check the index bigger than j.

    In situation 3, if numbers[i] + numbers[j] > target, because the array is sorted, we know that numbers[j*] < numbers[j], and j* < j. So we should check the index smaller than j.

    If the left index is not when i == 0, then where is j now?

    It should satisfy:
    numbers[i] + numbers[j] > target
    and
    numbers[i] + numbers[j - 1] < target

    Because answer is not found for i == 0, now let's check when i == 1.

    The trick is, now we only have to check the j that is smaller than the j we have when i == 0. If numbers[0] + numbers[j] > target, then also numbers[1] + numbers[j] > target. So j is decreasing.

    That's how 2 pointer solution come from. Start with i == 0, and j == numbers.length - 1, so that we can always decrease j as we increase i to find the solution.

    public class Solution {
        public int[] twoSum(int[] numbers, int target) {
            int[] res = new int[2];
            int l = 0, r = numbers.length - 1, cur = numbers[l] + numbers[r];
            while (l < r) {
                if (cur == target) {
                    res[0] = l + 1;
                    res[1] = r + 1;
                    break;
                } else if (cur < target) {
                    cur += numbers[l + 1] - numbers[l]; // increase the left index
                    l++;
                } else {
                    cur -= numbers[r] - numbers[r - 1]; // decrease the right index
                    r--;
                }
            }
            return res;
        }
    }
    

Log in to reply
 

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