[LintCode][2Sum] Triangle Count

Problem

More Discussions

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]

Given array S = [4,4,4,4], return 4. They are:

[4(1),4(2),4(3)]
[4(1),4(2),4(4)]
[4(1),4(3),4(4)]
[4(2),4(3),4(4)]

Solution

与2Sum的题目非常相似。先排序数组，然后枚举数a[k]，之后再a[0]..a[k-1]中找两个数，满足条件：a[i] + a[j] > a[k]。

由于 a[i] < a[j] < a[k]，所有我们可以保证:

• a[i] + a[k] > a[j]
• a[j] + a[k] > a[i]

class Solution {
public:
    /**
     * @param S: A list of integers
     * @return: An integer
     */
     
    int findSum(vector<int> &a, int beg, int end, int target) {
        int i = beg;
        int j = end;
        int count = 0;
        while (i < j) {
            int sum = a[i] + a[j];
            if (sum > target) {
                count += j - i;
                j--;
            } else {
                i++;
            }
        }
        
        return count;
    }
    
    int triangleCount(vector<int> &S) {
        int count = 0;
        sort(S.begin(), S.end());
        for(int k = 0; k < S.size(); k++) {
            count += findSum(S, 0, k - 1, S[k]);
        }
        return count;
    }
};