查找目标和3从和数组

Question

输入是一个排序数组和一个目标和。找到与目标相加的三个唯一元素的所有集合。

寻找最低订单(大O)。

A、B、C是排序数组的索引。A

从B= A + 1开始，在数组中一起移动AB。在C上搜索A的上限，然后遍历B和C到中间，测试A的所有可能性。

理论上更糟糕的情况是O(n * n)，但在实践中它接近$(n log n)，因为它使用对每个A的二进制搜索来限制C，然后它将B和C带到中间，从而避免了测试每一个B，C组合。对于每一个A，它首先检查它是否可能，这是非常经常的情况。

//test
List<int> rrr = Sum3(Enumerable.Range(0, 100).ToArray(), 150);
//end test

public static List<int> Sum3 (int[] input, int sum)
{
    //a,b,c are index to input 
    //start a = 0, b = 1 and solve for c
    //add b until over 
    //reduce c until under
    //a++ b=a+1

    if (input.Length < 3)
        throw new ArgumentOutOfRangeException();
    if (input[0] + input[1] + input[2] > sum)
        throw new ArgumentOutOfRangeException();
    if (input[input.Length - 1] + input[input.Length - 2] + input[input.Length - 3] < sum)
        throw new ArgumentOutOfRangeException();

    Array.Sort(input);
    List<int> result = new List<int>();
    int a = -1;
    int b = -1;
    int c = 2;
    int currentSum;

    while (true)  
    {
        a++;
        if (a == input.Length - 2)
            break;
        b = a + 1;
        if (input[a] + input[b] + input[b + 1] > sum)
            break;

        c = BinarySearch(input, sum - input[a] - input[b], b + 1, null);

        while(c > b)
        {
            currentSum = input[a] + input[b] + input[c];
            if (currentSum == sum)
            {
                result.Add(a);
                result.Add(b);
                result.Add(c);
                return result;
            }
            else if (currentSum < sum)
                b++;
            else
                c--;
        }
    }
    return null;
}

public static int BinarySearch(int[] A, int T, int? l, int? r)
{
    // Given an array A of n elements with values or records A0 ... An−1, sorted such that A0 ≤ ... ≤ An−1, and target value T, the following subroutine uses binary search to find the index of T in A.[6]
    // 1. Set L to 0 and R to n − 1.
    // 2. If L > R, the search terminates as unsuccessful.
    // 3. Set m(the position of the middle element) to the floor of (L + R) / 2.
    // 4. If Am < T, set L to m + 1 and go to step 2.
    // 5. If Am > T, set R to m – 1 and go to step 2.
    // 6. Now Am = T, the search is done; return m.
    Array.Sort(A);
    int M = -1;
    int L = l == null ? 0            : (int)l;
    int R = r == null ? A.Length - 1 : (int)r;
    while (L <= R)
    {
        M = (L + R) / 2;
        if (A[M] < T) L = M + 1;
        else if (A[M] > T) R = M - 1;
        else return M;
    }
    return M;
}

Answer 1

• 输入Sum3(int[] {3, 1, 1, 1, 0}, 3)错误。在对数组进行排序之前，这是假设要排序的数组。
• 当数组不够大和输入无效时，您会抛出相同的错误。您甚至没有添加字符串来说明错误是什么，所以这充其量只是个谜。
• 来自Python的我喜欢将函数保持为变异数据，或者不对其进行变异。这个函数可能需要一个排序数组作为输入，所以它只有一个负责任的数组。如果您希望使用一个未排序的数组，我将深入克隆该数组，这样您就不会影响其他地方的使用。
• 在while循环之外定义result充其量是令人困惑的，除了返回它时，您还会在其他地方使用它吗？不是吗？然后把它移到它使用的地方。然后，您可以将所有的result.Add's组合到get:返回新的List {a，b，c}；这清楚地显示了结果要么是null，要么包含三个数字。
• 我个人不喜欢你在某些情况下缺少支撑。如果我想再加一次，我就得做牙套了。这是一个琐碎的任务，但我的IDE冻结了，因为我在添加任何一个大括号时都必须犯大量语法错误。它阻止我编写buggy代码，因为如果我在if之后写了两行代码，我就不用担心了。这一切都是以按下一个按钮为代价的，在大多数IDE中，当您制作if时。我认为这个价格值得。

Answer 2

你的代码看起来很复杂。

首先，外部while循环不是while循环。这是一个for循环：

for (int a = 0; a < input.Length - 2; a++) ...。这样，意图就更清楚了。

代码的逻辑也很难理解。二进制搜索某个位置，然后向左或向右移动b和c。我搞不清到底怎么回事。我不确定密码是否正确。像a, b, c这样的名字也无济于事。它们是一些指数，但它们真正的含义是什么？我没有头绪。你为什么要使用二进制搜索？无论如何，在最坏的情况下，内部while在O(n)中工作。

我建议使用更明确的实现。这是我的伪码：

for mid = 1..(input.length - 2)
    high = mid + 1
    for low = (mid - 1)..0
        while high < input.length and input[low] + input[mid] + input[high] < sum:
            high += 1
        if high < input.length and input[low] + input[mid] + input[high] == sum:
            return [low, mid, high]
return []

这样，指数的含义就很清楚了。这也很清楚为什么high应该向右移动，而low要向左移动。没有必要处理任何角落的案件。

如果找不到目标和，我还建议返回一个空列表或null。我不认为抛出例外是合理的。找不到这笔钱是正常的，不是例外的情况。

Answer 3

我不会接受我自己的回答，但目前的情况是这样的。

public static List<int> Sum3 (int[] input, int sum)
{
    //a,b,c are index to input
    //start a = 0, b = 1 and solve for c
    //add b until over 
    //reduce c until under
    //when b=c the a++ b=a+1

    if (input.Length < 3)
        throw new ArgumentOutOfRangeException();
    //Array.Sort(input);
    if (input[0] + input[1] + input[2] > sum)
        throw new ArgumentOutOfRangeException();
    if (input[input.Length - 1] + input[input.Length - 2] + input[input.Length - 3] < sum)
        throw new ArgumentOutOfRangeException();

    int a = -1;
    int b = -1;
    int c = 2;
    int currentSum;
    for (a = 0; a < input.Length - 2; a++)
    {
        if (input[a] + input[input.Length - 1] + input[input.Length - 2] < sum)
            continue;

        b = a + 1;
        if (input[a] + input[b] + input[b + 1] > sum)
            break;
        c = BinarySearch(input, sum - input[a] - input[b], b + 1, null);
        while(c > b)
        {
            currentSum = input[a] + input[b] + input[c];

            if (currentSum == sum)
                return new List<int> { a, b, c };

            if (currentSum < sum)
                b++;
            else
                c--;
        }
    }
    return null;
}