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()