c++ - 在数组中查找所有三元组的总和为给定值。

这是我写的代码-

void FindTriplet(int arr[], int size, int x) {
    sort(arr,arr+size);
    for(int i=0;i<size-2;i++)
    {
        int l=i+1;
        int r=size-1;
        while(l<r)
        {
            int sum=arr[i]+arr[l]+arr[r];
            if(sum==x)
            {
                cout << arr[i] << " " << arr[l] << " " << arr[r] << endl;
                l++;
                r--;
            }
            else if(sum<x)
            {
                l++;
            }
            else
            {
                r--;
            }
        }
    }
}

O（n ^ 3）的复杂度是不可接受的。
但是此代码在以下情况下失败-
1 1 1 1其中要求的总和为3。
Ans。 1 1 1重复4次

最佳答案

找到正确的总和时，您确实可以处理重复项：

if (sum==x)
{
    // skip and count duplicates
    const auto oldL = l;
    do {
        ++l;
    } while (l <= r && arr[oldL] == arr[l]);
    const auto oldR = r;
    do {
        --r;
    } while (l <= r && arr[oldR] == arr[r]);

    // resulting count
    const auto count = (arr[oldL] == arr[oldR]
                       ? (l - oldL) * (l - oldL - 1) / 2
                       : ((l - oldL) * (oldR - r)));

    for (int j = 0; j != count; ++j) {
        std::cout << arr[i] << " " << arr[oldL] << " " << arr[oldR] << std::endl;
    }
}

Demo

关于c++ - 在数组中查找所有三元组的总和为给定值。，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/57501532/