Two Pointers

Posted on

一个很灵活的模式，有序与否都有应用的场景。需要根据题意来决定，while 循环的条件是 l < r 还是 l <= r。

In problems where we deal with sorted arrays (or linked lists) and need to find a set of elements that fulfill certain constraints, the Two Pointers approach becomes quite useful. The set of elements could be a pair, a triplet or even a subarray. For example, take a look at the following problem:

Given an array of sorted numbers and a target sum, find a pair in the array whose sum is equal to the given target.

To solve this problem, we can consider each element one by one (pointed out by the first pointer) and iterate through the remaining elements (pointed out by the second pointer) to find a pair with the given sum. The time complexity of this algorithm will be O(N^2) where “N” is the number of elements in the input array.

Given that the input array is sorted, an efficient way would be to start with one pointer in the beginning and another pointer at the end. At every step, we will see if the numbers pointed by the two pointers add up to the target sum. If they do not, we will do one of two things:

  • If the sum of the two numbers pointed by the two pointers is greater than the target sum, this means that we need a pair with a less sum. So, to try more pairs, we can decrement the end-pointer;
  • If the sum of the two numbers pointed by the two pointers is less than the target sum, this means that we need a pair with a greater sum. So, to try more pairs, we can increment the start-pointer;

Here is the visual representation of this algorithm:

The time complexity of the above algorithm will be O(N).

Snippets

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
nums.sort()
n = len(nums)

ans = []
for i in range(n):
    # handle duplicates
    if i > 0 and nums[i] == nums[i-1]:
        continue
    
    l, r = i + 1, n - 1
    while l < r:
        curr_sum = nums[i] + nums[l] + nums[r]
        if curr_sum == 0:
            ans.append([nums[i], nums[l], nums[r]])
            
            # move both pointers
            l += 1
            r -= 1
            while l < r and nums[l] == nums[l-1]:
                l += 1
            while l < r and nums[r] == nums[r+1]:
                r -= 1
        
        elif curr_sum < 0:
            l += 1
        else:
            r -= 1

return ans

LeetCode

167. Two Sum II - Input Array Is Sorted
26. Remove Duplicates from Sorted Array
977. Squares of a Sorted Array
15. 3Sum
16. 3Sum Closest
259. 3Sum Smaller
713. Subarray Product Less Than K
75. Sort Colors
18. 4Sum
844. Backspace String Compare
581. Shortest Unsorted Continuous Subarray