查找具有给定总和的元素对是否存在于大整数数组中

Question

我有一个包含1000万元元素的整数数组，如何在C＃中编写函数，如果数组中有一对总和最大为75，则返回True。

我的代码是：

 int sum = 75, max = 10000000; 
     int[] array = new int[max]; 
     bool checkFlag = false; 
     Random rnd = new Random(); 
     Stopwatch sw = Stopwatch.StartNew(); 

     for (int i = 0; i < max; i++) 
     { 
      array[i] = rnd.Next(0, max * 20); 
     } 
     Array.Sort(array); 
     if (array[0] + array[1] <= sum) 
     { 
      Console.WriteLine("{0} + {1} = {2}", array[0], array[1], array[0] + array[1]); 
      checkFlag = true; 
     } 
     Console.WriteLine("Sum upto 75 is: " + checkFlag); 

Answer 1

这将工作，如果数组排序。

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），不包括排序数组。

Answer 2

如果可以假设的数字是积极的，你可以这样做：

1. 创建75种元素的布尔数组。
2. 步行10,000,000个项目的列表。当你看到一个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); 
      } 
     } 

Answer 3

你可以做一个蛮力搜索。

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条件为真。 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(); 
} 

Answer 4

这是一个分类问题。你想要桶中的0与75s配对，1s与74s配对，等等。 Bucketing是一个字典jobby。 A Dictionary<int, List<int>>给你O（n）摊销的结果。如果你只关心bool结果，那么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）。

Answer 5

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(); 
     } 
    } 
}