9 Count Triangle Triple Index

kamia

O(n^2), since in the while loop, k always increasing instead of reset when a new j comes...

1.     // http://www.geeksforgeeks.org/find-number-of-triangles-possible/
   
2.     static int countTriangleTripleIndex(int [] A) {
   
3.         Arrays.sort(A);
   
4.         int cnt = 0;
   
5.         for(int i=0; i<=A.length-3; i++) {
   
6.             int k = i + 2;
   
7.             for(int j=i+1; j<A.length; j++) {
   
8.                 while(k<A.length && A【i】+A[j]>A[k])
   
9.                     k++;
   
10. 
    
11.                 cnt += Math.max(0, k-j-1);
    
12.             }
    
13.         }
    
14. 
    
15.         return cnt;
    
16.     }

复制代码

Sophia

Thanks for your sharing~~~

张正

需要加上一个对K值得判断，保证K值一直在最右边才可以通过。

1. class Solution {
   
2.         int countTriangleTripleIndex(int [] A) {
   
3.                 Arrays.sort(A);
   
4.                 int n = A.length;
   
5.                 int sum = 0;
   
6.                 for (int i = 0; i < n-2; i++) {
   
7.                         int k = i + 2;
   
8.                         for(int j = i + 1; j < n - 1; j++) {
   
9.                                 if ( k <= j )
   
10.                                         k = j + 1;
    
11.                                 while((k < n) && (A【i】 + A[j] > A[k]))
    
12.                                         k++;
    
13.                                 sum += k - j - 1;
    
14.                         }
    
15.                 }
    
16.                 return sum;
    
17.         }
    
18. }

复制代码