无脑上暴力破解解法:
class Solution {
public:
int countGoodTriplets(vector<int>& arr, int a, int b, int c) {
int res = 0,n = arr.size();
for(int i = 0;i < n;i++)
{
for(int j = i + 1;j < n;j++)
{
for(int k = j + 1;k < n;k++)
{
if(abs(arr[i] - arr[j]) <= a &&
abs(arr[j] - arr[k]) <= b &&
abs(arr[i] - arr[k]) <= c )
res++;
}
}
}
return res;
}
};
运行结果正确,性能参数符合预期:
Runtime: 92 ms, faster than 5.15% of C++ online submissions for Count Good Triplets.
Memory Usage: 8.5 MB, less than 10.04% of C++ online submissions for Count Good Triplets.
对上面无脑暴力破解的算法进行优化,优化后的算法时间复杂度依然是n的三次方,运行结果击败80%用户。
Runtime: 32 ms, faster than 76.87% of C++ online submissions for Count Good Triplets.
Memory Usage: 8.5 MB, less than 9.74% of C++ online submissions for Count Good Triplets.
class Solution {
public:
int countGoodTriplets(vector<int>& arr, int a, int b, int c) {
int res = 0,n = arr.size();
for(int i = 0;i < n - 2;i++)
{
for(int j = i + 1;j < n - 1;j++)
{
if (abs(arr[i] - arr[j]) > a )
continue;
for(int k = j + 1;k < n;k++)
{
if(abs(arr[j] - arr[k]) <= b &&
abs(arr[i] - arr[k]) <= c )
res++;
}
}
}
return res;
}
};