[LintCode 382]は、三角形の3つの辺の長さを表す3つの数を探している整数配列を与え、このような3つの数のセットを探して三角形を構成することができますか?
サンプル
例えば、所与の配列S=
ここで見つけられる3つの三角形は次のとおりです.
例えば、所与の配列S=
{3,4,6,7}は、3を返すここで見つけられる3つの三角形は次のとおりです.
{3,4,6} {3,6,7} {4,6,7}
S = {4,4,4,4}、4を します.
ここで つけられる3つの は のとおりです.{4(1),4(2),4(3)} {4(1),4(2),4(4)} {4(1),4(3),4(4)} {4(2),4(3),4(4)}
/**
* @param S: A list of integers
* @return: An integer
*/
//Solution 1 , , ,
O(n^3)，
int
triangleCount1(
vector
<
int
> &
S
) {
// write your code here
int
iSize =
S
.size();
if
(iSize <= 2)
{
return
0;
}
int
sum = 0;
for
(
int
i = 0; i < iSize - 2; i++)
{
int
a =
S
.at(i);
for
(
int
j = i + 1; j < iSize - 1; j++)
{
int
b =
S
.at(j);
for
(
int
k = j + 1; k < iSize; k++)
{
int
c =
S
.at(k);
if
(a + b > c && a + c > b && b + c > a)
sum++;
}
}
}
cout
<<
"sum = "
<<
sum;
return
sum;
}
//Solution 2 , , O(n^2)， vector ， ，
int
triangleCount(
vector
<
int
> &
S
) {
// write your code here
int
iSize =
S
.size();
if
(iSize <= 2)
{
return
0;
}
int
sum = 0;
sort(
S
.begin(),
S
.end());
for
(
int
i = 2; i < iSize; i++)
{
int
posLeft = 0;
int
posRight = i - 1;
int
c =
S
.at(i);
while
(posLeft < posRight)
{
if
(
S
.at(posLeft) +
S
.at(posRight) <= c)
posLeft++;
else
if
(
S
.at(posLeft) +
S
.at(posRight) > c)
{
sum += posRight - posLeft;
posRight--;
}
}
}
return
sum;
}