Triangle Count

题目：

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: Given array S = [3,4,6,7], return 3. They are:

[3,4,6]

[3,6,7]

[4,6,7]

分析：

解法1包含了two pointer的思想所以复杂度是n^2，如果用解法2枚举，则复杂度为n^3，大数据会超时。

解法1：

class Solution {
public:
    /**
     * @param S: A list of integers
     * @return: An integer
     */
    int triangleCount(vector<int> &S) {
        // write your code here
        sort(S.begin(), S.end() );
        int start = 0;
        int end = S.size() - 1;
        int res = 0;
        for (int i = 0; i < S.size(); i++) {
            start = 0;
            end = i - 1;
            while (start < end) {
                if (S[start] + S[end] > S[i]) {
                    res += end - start;
                    end--;
                } else {
                    start++;
                }
            }
        }
        return res;
    }
};

解法2：

class Solution {
public:
    /**
     * @param S: A list of integers
     * @return: An integer
     */
    int triangleCount(vector<int> &S) {
        // write your code here
        sort(S.begin(), S.end() );
        int res = 0;
        for (int i = 0; i < S.size(); i++) {
            for (int j = i + 1; j < S.size() - 1; j++) {
                int k = j + 1;
                while (k < S.size() && S[i] + S[j] > S[k]) {
                    k++;
                }
                res += k - j - 1;
            }
        }
        return res;
    }
};