Lintcode 382. Triangle Count

382. Triangle Count

中文English

Given an array of integers, how many three numbers can be found in the array, so that we can build an triangle whose three edges length is the three numbers that we find?

Example

Example 1:

Input: [3, 4, 6, 7]
Output: 3
Explanation:
They are (3, 4, 6), 
         (3, 6, 7),
         (4, 6, 7)

Example 2:

Input: [4, 4, 4, 4]
Output: 4
Explanation:
Any three numbers can form a triangle. 
So the answer is C(3, 4) = 4

Code (Java):

public class Solution {
    /**
     * @param S: A list of integers
     * @return: An integer
     */
    public int triangleCount(int[] S) {
       if (S == null || S.length < 3) {
           return 0;
       }

       int ans = 0;
       Arrays.sort(S);
       
       for (int i = S.length - 1; i >= 2; i--) {
           int lo = 0;
           int hi = i - 1;

           while (lo < hi) {
               if (S[lo] + S[hi] <= S[i]) {
                   lo++;
               } else {
                   ans += hi - lo;
                   hi--;
               }
           }
       }

       return ans;
    }
}