Share the joy

Given an array with all positive numbers.

Find how many number of group are there which is able to make a triangle.

For example,

Given {3, 4, 5}, return 1

Given {3, 4, 5, 6}, return 4. Possible triangles are: {4, 5, 6}, {3, 5, 6}, {3, 4, 6}, {3, 4, 5}

The solution is that make 3 pointers, i<j<k. For each group of i, j, find the k position, where k is the first position at the right of j, wherearr[i]+arr[j]<=arr[k]. In this way arr[i], arr[j], arr[[j+1, j+2,…,k-1]] can group a triangle.

Take arr={4, 5, 6, 7, 8, 9, 10} for example, the 3 pointers moving is like below:

The tricky part is that for each round of i, the k keeps moving to right, never moves back to left. We can use this to do k++ in each round of j.

check my code on github: link

Pingback: 3 Sum Smaller | allenlipeng47()