Number of combination of triangle

By | December 23, 2015
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