# L15-CountTriangles
###### tags: `Codility_lessons`
## Question
https://app.codility.com/programmers/lessons/15-caterpillar_method/count_triangles/
## Key
1. 重點在於怎麼去迭帶3個變數P, Q, R，去嘗試所有可能性比較三邊長
2. 法二的寫法比較直觀，法一的寫法比較進階
## Reference
## Solution
### solution I

#include <algorithm>

int solution(vector<int> &A) {
    if (A.size() < 3)
        return 0;
    int count = 0;
    sort(A.begin(), A.end());
    auto P = A.begin();

    while (P <= A.end()-3) {
        auto Q = P + 1;
        auto R = Q + 1;
        while (R < A.end()) {
            if (*P + *Q > *R) {
                count += R - Q;
                R++;
            }
            else if (Q < R - 1)
                Q++;
            else
                R++;
        }
        P++;
    }
    return count;
}

### solution II

#include<algorithm>

int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    int size = A.size(), cnt = 0;
    if (size <3) {
        return 0;    
    }
    
    sort(A.begin(), A.end());
    
    for (int i = 0; i < size - 2; i++) {
        int end = i + 2;
        for (int j = i + 1; j < size - 1; j++) {
            while (end < size && A[i] + A[j] > A[end]) 
            {
                end++;
            }
            cnt += (end - j - 1);
        }
    }
    return cnt;
}