Поиск целочисленной суммы в массиве из 1 000 000

Question

Учитывая большой список целых чисел (более 1 000 000 значений), найдите, сколько способов выбрать два из них, которые составляют до 0 .... Является ли вопрос

То, что я сделал, это создать положительный список случайного целого:

Random pos = new Random(); 
int POSNO = pos.Next(1, 1000000); 
lstPOS.Items.Add(POSNO); 
lblPLus.Text = lstPOS.Items.Count.ToString(); 
POSCount++; 

И создал негативный список:

Random neg = new Random(); 
int NEGNO = neg.Next(100000, 1000000); 
lstNEG.Items.Add("-" + NEGNO); 
lblNegative.Text = lstNEG.Items.Count.ToString(); 
NegCount++; 

Чтобы сделать сумму проверки я использую:

foreach (var item in lstPOS.Items) 
{ 
    int POSItem = Convert.ToInt32(item.ToString()); 
    foreach (var negItem in lstNEG.Items) 
    { 
     int NEGItem = Convert.ToInt32(negItem.ToString()); 
     int Total = POSItem - NEGItem; 
     if (Total == 0) 
     { 
      lstADD.Items.Add(POSItem + "-" + NEGItem + "=" + Total); 
      lblAddition.Text = lstADD.Items.Count.ToString(); 
     } 
    } 
} 

Я знаю, что это не самый быстрый маршрут. Я рассмотрел использование массива. Есть ли у вас какие-либо предложения?

Answer 1

Вы попытались избежать проверки близких близких чисел (1, 2, 3, 4), но вы не избегаете проверки типа (-100000, 1), (-1, 100000). Сложность времени - O (n^2). Чтобы избежать этого, вам нужно сначала отсортировать их, а затем выполнить поиск с двух сторон.

var random = new Random(); 
var input = Enumerable.Range(1, 100).Select(_ => random.Next(200) - 100).ToArray(); 

Array.Sort(input); // This causes most computation. Time Complexity is O(n*log(n)); 
var expectedSum = 0; 
var i = 0; 
var j = input.Length - 1; 
while (i < j) // This has liner time complexity O(n); 
{ 
    var result = input[i] + input[j]; 
    if(expectedSum == result) 
    { 
     var anchori = i; 
     while (i < input.Length && input[i] == input[anchori]) 
     { 
      i++; 
     } 
     var anchorj = j; 
     while (j >= 0 && input[j] == input[anchorj]) 
     { 
      j--; 
     } 
     // Exclude (self, self) combination 
     Func<int, int, int> combination = (n, k) => 
     { 
      var mink = k * 2 < n ? k : n - k; 
      return mink == 0 ? 1 
       : Enumerable.Range(0, mink).Aggregate(1, (x, y) => x * (n - y)) 
       /Enumerable.Range(1, mink).Aggregate((x, y) => x * y); 
     }; 
     var c = i < j ? (i - anchori) * (anchorj - j) : combination(i - anchori, 2); 
     for (int _ = 0; _ < c; _++) 
     { 
      // C# 6.0 String.Format 
      Console.WriteLine($"{input[anchori]}, {input[anchorj]}"); 
     } 
    } 
    else if(result < expectedSum) { 
     i++; 
    } 
    else if(result > expectedSum) { 
     j--; 
    } 
} 

Answer 2

Самый быстрый способ без сортировки !.

Прежде всего, вы знаете, что сумма двух целых чисел равна 0, если они имеют , равное абсолютное значение, но одно отрицательное, а другое положительное. Так что вам не нужно сортировать. что вам нужно, это положительный список Intersect с отрицательным списком (путем сравнения абсолютного значения). результатом являются числа, которые заканчиваются 0 суммой.

Intersect имеет временную сложность O(n+m) где n - размер первого списка, а m - размер второго.

private static void Main(string[] args) 
{ 
    Random random = new Random(); 

    int[] positive = Enumerable.Range(0, 1000000).Select(n => random.Next(1, 1000000)).ToArray(); 
    int[] negative = Enumerable.Range(0, 1000000).Select(n => random.Next(-1000000, -1)).ToArray(); 

    var zeroSum = positive.Intersect(negative, new AbsoluteEqual()); 

    foreach (var i in zeroSum) 
    { 
     Console.WriteLine("{0} - {1} = 0", i, i); 
    } 
} 

Вам также необходимо использовать этот IEqualityComparer.

public class AbsoluteEqual : IEqualityComparer<int> 
{ 
    public bool Equals(int x, int y) 
    { 
     return (x < 0 ? -x : x) == (y < 0 ? -y : y); 
    } 

    public int GetHashCode(int obj) 
    { 
     return obj < 0 ? (-obj).GetHashCode() : obj.GetHashCode(); 
    } 
} 

Answer 3

Давайте посмотрим; ваш массив что-то вроде этого:

int[] data = new int[] { 
    6, -2, 3, 2, 0, 0, 5, 7, 0, -2 
    }; 

вы можете добавить до нуля двумя различными способами:

1. а + (-a) // положительное + отрицательное
2. 0 + 0 // любые две нулей

в приведенном выше примере Там вы пять пара:

-2 + 2 (two pairs): [1] + [3] and [3] + [9] 
    0 + 0 (three pairs): [4] + [5], [4] + [8] and [5] + [8] 

Таким образом, вы должны отслеживать положительные/отрицательные пары и нули. Реализация

Dictionary<int, int> positives = new Dictionary<int, int>(); 
Dictionary<int, int> negatives = new Dictionary<int, int>(); 
int zeros = 0; 

foreach(var item in data) { 
    int v; 

    if (item < 0) 
    if (negatives.TryGetValue(item, out v))  
     negatives[item] = negatives[item] + 1; 
    else 
     negatives[item] = 1; 
    else if (item > 0) 
    if (positives.TryGetValue(item, out v))  
     positives[item] = positives[item] + 1; 
    else 
     positives[item] = 1; 
    else 
    zeros += 1; 
} 

// zeros: binomal coefficent: (2, zeros) 
int result = zeros * (zeros - 1)/2; 

// positive/negative pairs 
foreach (var p in positives) { 
    int n; 

    if (negatives.TryGetValue(-p.Key, out n)) 
    result += n * p.Value; 
} 

// Test (5) 
Console.Write(result); 

Обратите внимание, что нет сортировки и словари (т.е. хэш-таблицы) используются для позитивов и негативов поэтому время выполнения будет линейной, O(n); темная сторона реализации состоит в том, что требуются две дополнительные структуры (то есть дополнительная память).В вашем случае (только миллионы целых чисел - мегабайты) у вас есть эта память.

Редактировать: terser, но менее читаемым раствор Linq:

var dict = data 
    .GroupBy(item => item) 
    .ToDictionary(chunk => chunk.Key, chunk => chunk.Count()); 

    int result = dict.ContainsKey(0) ? dict[0] * (dict[0] - 1)/2 : 0; 

    result += dict 
    .Sum(pair => pair.Key > 0 && dict.ContainsKey(-pair.Key) ? pair.Value * dict[-pair.Key] : 0); 

Answer 4

Вот еще одно решение, использующее (да) LINQ. Надеюсь, что код сам объяснительное

Сначала некоторые данные

var random = new Random(); 
var data = new int[1000000]; 
for (int i = 0; i < data.Length; i++) data[i] = random.Next(-100000, 100000); 

А теперь решение

var result = data 
    .Where(value => value != int.MinValue) 
    .GroupBy(value => Math.Abs(value), (key, values) => 
    { 
     if (key == 0) 
     { 
      var zeroCount = values.Count(); 
      return zeroCount * (zeroCount - 1)/2; 
     } 
     else 
     { 
      int positiveCount = 0, negativeCount = 0; 
      foreach (var value in values) 
       if (value > 0) positiveCount++; else negativeCount++; 
      return positiveCount * negativeCount; 
     } 
    }) 
    .Sum(); 

Теоретически выше должно быть O (N) времени и O (M) пространство сложности, где M - это счетчик уникальных абсолютных значений в списке.