查找大整数数组中是否存在一对给定和的元素

这是一个装箱问题。你想要0的桶与75的桶配对，1的桶与74的桶配对等等。Bucketing是Dictionary的工作。Dictionary<int, List<int>>给出了O（n）摊销的结果。如果你只关心布尔结果，那么HashSet<int>就足够了。没有比O（n）更好的了。

    static bool PairExists(int[] arr, int sum) {
        var set = new HashSet<int>();
        foreach (int elem in arr) set.Add(elem);
        foreach (int elem in set)
            if (set.Contains(sum - elem)) return true;
        return false;
    }

如果数组可能包含该对，那么您可以考虑在Add（）调用之后进行测试，仍然是O（n）。

如果对数组进行排序，这将起作用。

public bool ContainsPair(int[] array) 
{
    int i = 0;
    int j = array.Length - 1;
    while(i < j)
    {
        if (array[i] + array[j] == 75) 
            return true;
        else if (array[i] + array[j] <  75) 
            i++;
        else if (array[i] + array[j] >  75) 
            j--;
    }
    return false;
}

您使用两个指针，然后走向数组的中间。指针i从数组的开头开始，而j从数组的末尾开始。如果你找到两个总数为75的数字，你就会返回true。如果总和小于75，则将指针i向中间移动一步，然后再次检查。如果总和大于75，则将指针j向中间移动一步，然后再次检查。

如果两个指针相遇，则返回false，因为没有找到对。

这是O（n），不包括对数组进行排序。

您可以进行强力搜索。

public bool hasPairOf(int[] a, int sum)
{
   for(int i=0; i < a.length-1; i++)
   {
      if(a[i]+a[i+1] == sum)
         return true;
   }
   return false;
}

或者，您可以创建一个枚举器并使用LINQ。

public static IEnumerate<int> toSums(this int[] a)
{
   for(int i=0; i < a.length-1; i++)
   {
      yield return a[i]+a[i+1];
   }
}

现在您可以执行以下操作。

a.toSums().Any(pair=>pair == 75);

两者应该具有相同的性能。如果你问为什么？这是因为C#只会执行枚举器，直到Any条件为true。toSums函数使用yield关键字创建一个枚举器，该枚举器仅在计算时执行。

编辑：

在数组中查找总和为75的任意一对值，而不仅仅是相邻值。为了更容易阅读，我只会使用LINQ。

function bool hasPairOf(int[] a, int sum)
{
    var nums = a.Where(val=>val <= sum)
                .Select((v,i)=>new{value=v,index=i})
                .ToArray();
    return (from a1 in nums
            from a2 in nums
            where a1.index != a2.index
                  && a1.value+a2.value == sum
            select true).FirstOrDefault();
}

如果你可以假设数字是正数，你可以这样做：

1. 创建一个包含75个元素的布尔数组
2. 浏览包含10000000个项目的列表。当你看到一个75岁或以下的人：
   • 检查boolean arry在元素75处有一个条目，即该数字。如果是，你就找到了匹配项
   • 否则，设置布尔数组的第n个条目

示例C#：

        var bits = new bool[75];
        foreach (var n in intArray)
        {
            if (n <= 75)
            {
                var diff = 75 - n;
                if (bits[diff - 1])
                {
                    MessageBox.Show(string.Format("Found pair: {0} and {1}", n, diff));
                    break;
                }
                bits[n - 1] = true;
            }
        }

但是，如果数组中的数字可以是任何有效的整数，包括负数，则可以执行以下操作：

        var set = new HashSet<int>();
        foreach (var n in intArray)
        {
            if (n <= 75)
            {
                var diff = 75 - n;
                if (set.Contains(diff))
                {
                    MessageBox.Show(string.Format("Found pair: {0} and {1}", n, diff));
                    break;
                }
                set.Add(n);
            }
        }

using System;
using System.Diagnostics;
using System.Linq;
using System.Collections.Generic;
namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            const int max = 10000000;
            const int sum = 75;
            var data = new int[max];
            var rnd = new Random();
            bool found = false; 
            int c = 1;
            Stopwatch sw;
            while (!found)
            {
                sw = Stopwatch.StartNew();
                for (int i = 0; i < max; ++i)
                {
                    data[i] = rnd.Next(0, max*25);
                }
                sw.Stop();
                Console.WriteLine("Took {0}ms to create the array", sw.ElapsedMilliseconds);
                sw = Stopwatch.StartNew();
                var check75 = new HashSet<int>(data.Where(x => x <= 75));
                sw.Stop();
                Console.WriteLine("Took {0}ms to create the hashset", sw.ElapsedMilliseconds);
                sw = Stopwatch.StartNew();
                for (int i = 0; i < max; ++i)
                {
                    if (check75.Contains(sum - data[i]))
                    {
                        Console.WriteLine("{0}, {1} ", i, data[i]);
                        found = true;
                    }
                }
                sw.Stop();
                Console.WriteLine("Took {0}ms to check75", sw.ElapsedMilliseconds);
                Console.WriteLine("Loop #" + c++);
            }
            Console.WriteLine("Finish");
            Console.ReadKey();
        }
    }
}

如果Dictionary中没有，则在其中添加总和的赞美。如果Dictional中已经有赞美，则给定总和存在一对。

    public bool HasPair(List<int> arr, int sum)
    {
        var track = new Dictionary<int, int>();
        for (var i = 0; i < arr.Count; i++)
        {
            if (track.ContainsKey(arr[i]))
                return true;
            
            track.Add(sum - arr[i], arr[i]);
        }
        return false;
    }