查找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

让我们来看看; 你的数组是这样的:

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

您可以通过两种不同的方式添加到零:

1. a +(-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 2

您试图避免检查两个接近的数字（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--;
    }
}