Given an array [4 2 1 3 5], and a target. Return the number of pairs that the sum is greater than or equal to 5.
Technique: 1. sort, 2. use two pointers.
1. Order is not fixed. [2, 3], [3, 2] are different. [3, 3] is ok.
[1 2 3 4 5]
[1, 4] -> [1, 4], [1, 5]
[2, 3] -> [2, 3], [2, 4], [2, 5]
[3, 2] -> [3, 2], [3, 3], [3, 4], [3, 5]
[4, 1] -> [4, 1], [4, 2], [4, 3], [4, 4], [4, 5]
[5, 1] -> [5, 1], [5, 2], [5, 3], [5, 4], [5, 5]
2. Pair order are fixed. v0 < v1
[1 2 3 4 5]
[a, b]
[1, 4] -> [1, 4], [1, 5]
[2, 3] -> [2, 3], [2, 4], [2, 5]
[3, 2] -> [3, 2], [3, 3], [3, 4], [3, 5]
[4, 1] -> [4, 1], [4, 2], [4, 3], [4, 4], [4, 5]
[5, 1] -> [5, 1], [5, 2], [5, 3], [5, 4], [5, 5]
for each loop, the ans is len – Math.max(a, b). Or in another word, we only pick the one with a < b to avoid duplicate.
Related: https://www.youtube.com/watch?v=9pAVTzVYnPc