1.4.15

上次更新:2019-04-17
发现了题解错误/代码缺陷/排版问题?请点这里:如何:提交反馈

解答

由于数组已经排序(从小到大),负数在左侧,正数在右侧。
TwoSumFaster
设最左侧下标为 lo,最右侧下标为 hi。
如果 a[lo] + a[hi] > 0, 说明正数太大,hi–。
如果 a[lo] + a[hi] < 0,说明负数太小,lo++。
否则就找到了一对和为零的整数对,lo++, hi–。

ThreeSumFaster
对于数组中的每一个数 a,ThreeSum 问题就等于求剩余数组中所有和为 -a 的 TwoSum 问题。
只要在 TwoSumFaster 外层再套一个循环即可。

代码

/// <summary>
/// TwoSum 的快速实现。(线性级别)
/// </summary>
/// <param name="a">需要查找的数组范围。</param>
/// <returns>数组中和为零的整数对数量。</returns>
static int TwoSumFaster(int[] a)
{
    int lo = 0;
    int hi = a.Length - 1;
    int count = 0;
    while (lo < hi)
    {
        if (a[lo] + a[hi] == 0)
        {
            count++;
            lo++;
            hi--;
        }
        else if (a[lo] + a[hi] < 0)
        {
            lo++;
        }
        else
        {
            hi--;
        }
    }
    return count;
}

/// <summary>
/// ThreeSum 的快速实现。(平方级别)
/// </summary>
/// <param name="a">需要查找的数组范围。</param>
/// <returns>数组中和为零的三元组数量。</returns>
static int ThreeSumFaster(int[] a)
{
    int count = 0;
    for (int i = 0; i < a.Length; ++i)
    {
        int lo = i + 1;
        int hi = a.Length - 1;
        while (lo <= hi)
        {
            if (a[lo] + a[hi] + a[i] == 0)
            {
                count++;
                lo++;
                hi--;
            }
            else if (a[lo] + a[hi] + a[i] < 0)
            {
                lo++;
            }
            else
            {
                hi--;
            }
        }
    }
    return count;
}
上一题 下一题