1.4.14

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

解答

这里给出暴力方法,将最内侧循环换成二分查找即为优化版本。

代码

using System;

namespace Measurement
{
    /// <summary>
    /// 用暴力方法查找数组中和为零的四元组。
    /// </summary>
    public static class FourSum
    {
        /// <summary>
        /// 输出数组中所有和为 0 的四元组。
        /// </summary>
        /// <param name="a">包含所有元素的数组。</param>
        public static void PrintAll(long[] a)
        {
            int N = a.Length;
            for (int i = 0; i < N; ++i)
            {
                for (int j = i + 1; j < N; ++j)
                {
                    for (int k = j + 1; k < N; ++k)
                    {
                        for (int l = k + 1; l < N; ++l)
                        {
                            if (a[i] + a[j] + a[k] + a[l] == 0)
                            {
                                Console.WriteLine($"{a[i]} + {a[j]} + {a[k]} + {a[l]} = 0");
                            }
                        }
                    }
                }
            }
        }

        /// <summary>
        /// 计算和为零的四元组的数量。
        /// </summary>
        /// <param name="a">包含所有元素的数组。</param>
        /// <returns></returns>
        public static int Count(long[] a)
        {
            int N = a.Length;
            int cnt = 0;

            for (int i = 0; i < N; ++i)
            {
                for (int j = i + 1; j < N; ++j)
                {
                    for (int k = j + 1; k < N; ++k)
                    {
                        for (int l = k + 1; l < N; ++l)
                        {
                            if (a[i] + a[j] + a[k] + a[l] == 0)
                            {
                                cnt++;
                            }
                        }
                    }
                }
            }

            return cnt;
        }
    }
}

另请参阅

Measurement 库

上一题 下一题