Count the number of possible triangles

4.cpp

// As though it looks like O(n^3) but it actally is O(n^2). because of k initialized outisde and does not depenv on j value.

int possible_triangles(vector<int> a){
  int count = 0;
  for(int i=0; i<n-2; i++){
    int k = i+2;
    for(int j=i+1; j<n; j++){
      while(k < n && a[i] + a[j] > a[k]) ++k;
      count = count + (k-j-1);
    }
  }
  return count;
}