查找具有給定總和的元素對是否存在於大整數數組中

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