arrays - 确定数组中是否存在 a、b、c 以使 a+b+c = z 的算法？

Question

<分区>

Answer 1

该方法与求 a 和 b 的和 z 非常相似。

首先对数组进行排序。然后将 a 固定在位置 i 并检查是否在 i + 1 到 n

范围内有 sumz-a

因为你有一个 O(n) 算法来检查 z 是否存在 a 和 b。我们只扩展它来修复 a 并检查是否可以使用另外两个变量来产生总和。总运行时间为 O(n^2)

来自 here

// returns true if there is triplet with sum equal
// to 'sum' present in A[]. Also, prints the triplet
bool find3Numbers(int A[], int arr_size, int sum)
{
    int l, r;

    /* Sort the elements */
    sort(A, A+arr_size);

    /* Now fix the first element one by one and find the
       other two elements */
    for (int i=0; i<arr_size-2; i++)
    {

        // To find the other two elements, start two index
        // variables from two corners of the array and move
        // them toward each other
        l = i + 1; // index of the first element in the
                   // remaining elements
        r = arr_size-1; // index of the last element
        while (l < r)
        {
            if( A[i] + A[l] + A[r] == sum)
            {
                printf("Triplet is %d, %d, %d", A[i], 
                                         A[l], A[r]);
                return true;
            }
            else if (A[i] + A[l] + A[r] < sum)
                l++;
            else // A[i] + A[l] + A[r] > sum
                r--;
        }
    }

    // If we reach here, then no triplet was found
    return false;
}