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?
Have you met this question in a real interview?
Yes
Example
Given array S =[3,4,6,7], return3. They are:
[3,4,6]
[3,6,7]
[4,6,7]
Given array S =[4,4,4,4], return4. 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)]
class Solution {
public:
/\*\*
\* @param S: A list of integers
\* @return: An integer
\*/
int triangleCount\(vector<int> &S\) {
// write your code here
int cnt = 0;
sort\(S.begin\(\), S.end\(\)\);
for \(int k=2; k < S.size\(\); ++k\){
int i = 0, j = k - 1;
int target = S\[k\];
while \(i < j\) {
if \(S\[i\]+S\[j\] > target\) {
cnt += j - i;
--j;
} else {
++i;
}
}
}
return cnt;
}
};