LeetCode Q259: 3Sum Smaller

Given an array of n integers nums and a target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.

For example, given nums = [-2, 0, 1, 3], and target = 2.

Return 2. Because there are two triplets which sums are less than 2:

[-2, 0, 1]
[-2, 0, 3]

Follow up:
Could you solve it in O(n2) runtime?

Solution:

Use two technique of two pointers. The outter loop loop over all elements in the sorted array. in the loop, use two pointers to decide the count. When using two pointers. No need to iterate over all valid case. Because once we find the first valid pair, we can just count how many numbers are there in between this pair. 

On extra trick is to use early stop when v0 > target/3.

Round 2 Solution