用C++编写的计算小于给定值的三元组计数程序

给定一个不重复整数数组和一个和值，找到和小于给定和值的三元组的数量。预期时间复杂度为O(n 2 )。

例子：

输入 : arr[] = {-2, 0, 1, 3}
        和值 = 2。
输出 ：2
解释 ： 以下是和小于2的三元组
               (-2, 0, 1) 和 (-2, 0, 3) 

输入 : arr[] = {5, 1, 3, 4, 7}
        和值 = 12。
输出 ：4
解释 ： 以下是和小于12的三元组
               (1, 3, 4), (1, 3, 5), (1, 3, 7) 和 
               (1, 4, 5)

用三个循环考虑每个三元组并逐个比较它们的和，如果三元组的和小于所给和值，则将计数器加1。

// 一个简单的C ++程序，用于计算小于给定值的三元组
// 需要包含所有的头文件
#include<bits/stdc++.h>
using namespace std;
 
int countTriplets(int arr[], int n, int sum)
{
    // 初始化结果
    int ans = 0;
 
    // 将数组的第一个元素作为A[i]
    for (int i = 0; i < n-2; i++)
    {
       // 将数组的第二个元素作为A[j]
       for (int j = i+1; j < n-1; j++)
       {
           // 查询第三个元素
           for (int k = j+1; k < n; k++)
               if (arr[i] + arr[j] + arr[k] < sum)
                   ans++;
       }
    }
 
    return ans;
}
 
// 主函数
int main()
{
    int arr[] = {5, 1, 3, 4, 7};
    int n = sizeof arr / sizeof arr[0];
    int sum = 12;
    cout << countTriplets(arr, n, sum) << endl;
    return 0;
}

输出：

时间复杂度： O(n 3 )

辅助空间： O(1)

因为只用到了常数的额外空间，一个 更有效的解决方案 是通过首先对数组进行排序，然后使用本篇文章中的方法1来循环计算三元组数量，时间复杂度为O(n 2 )。

1) 按升序排列输入数组。
2) 将结果初始化为0。
3) 设置循环i从0到n-2。 迭代此循环将以arr[i]为第一个元素的所有三元组找到。
     a) 将另外两个元素初始化为子数组的端点元素arr[i+1..n-1]，即 j = i+1 且 k = n-1
     b) 将j和k向中间靠拢，直到它们相遇，即当(j= sum
                时，减小k
            //否则，对于当前的i和j，可能有（k-j）个第三个元素满足约束条件。
            // （ii）否则，执行ans += (k - j)，然后j++。

下面是上述想法的具体实现。

// C++程序：计算小于给定值的三元组
#include<bits/stdc++.h>
using namespace std;
 
int countTriplets(int arr[], int n, int sum)
{
    // 排序输入数组
    sort(arr, arr+n);
 
    // 初始化结果
    int ans = 0;
 
    // 每次循环迭代计数带有三元组的
    // 第一个元素为arr[i]
    for (int i = 0; i < n - 2; i++)
    {
        // 初始化其他两个元素为子数组arr[j+1..k]的角元素
        int j = i + 1, k = n - 1;
 
        // 使用Meet in the Middle概念
        while (j < k)
        {
            // 如果当前三元组的总和更大或相等，
            // 将右角移到查找更小的值
            if (arr[i] + arr[j] + arr[k] >= sum)
                k--;
 
            // 否则左角移动
            else
            {
                // 这很重要，对于当前i和j，有
                // 可以总共k-j个第三个元素。
                ans += (k - j);
                j++;
            }
        }
    }
    return ans;
}
 
//主程序
int main()
{
    int arr[] = {5, 1, 3, 4, 7};
    int n = sizeof arr / sizeof arr[0];
    int sum = 12;
    cout << countTriplets(arr, n, sum) << endl;
    return 0;
}

输出：

时间复杂度： O(n 2 )

辅助空间： O(1)

由于使用常量额外空间。