c# - HashSet 的两个总和问题不适用于重复项

Question

我正在做一项作业，我必须在平均/最佳 O(n) 或线性运行时复杂度下找到总和为“x”的数字对。我不能使用蛮力，因为它会增加复杂性。

我正在使用 HashSet 并使用 contains 方法检查是否可以找到 (x - array[i]) 并打印它。但是包含对整个 HashSet 的方法检查，我想在每次迭代的第“i”个位置之后开始搜索。另外，我无法对它们进行排序，因为我必须按照它们在输入数组中出现的顺序打印它们。

          if (hSet.Contains(x - array[i]))
             {
                 Console.Write("(" + array[i] + "," + (x - array[i]) + ")");
                        hSet.Add(array[i]);

                }
             }

使用输入数组 { 1, 6, 3, 2, 5, 5, 7, 8, 4, 8, 2, 5, 9, 9, 1 };

我的输出 (1,9)(6,4)(3,7)(2,8)(5,5)(5,5)(7,3)(8,2)(4,6) (8,2)(2,8)(5,5)(9,1)(9,1)

预期输出:(1,9), (1,9), (6,4), (3,7), (2,8), (2,8), (5,5), (5 ,5), (5,5), (8,2), (8,2), (9,1), (9,1)

Answer 1

此代码按照您的预期工作，复杂度为 O(n)(在大多数情况下)。使用 Dictionary，而不是 HashSet。

• 首先，从数组构建字典，键是项目，值是项目的计数。

• 之后，迭代项目，用字典检查它并产生输出。同时减少Dictionary中此项的计数，避免以后不必要的输出。

代码如下:

using System;
using System.Collections.Generic;

class MainClass {
    public static void Main (string[] args) {
        int[] array = { 1, 6, 3, 2, 5, 5, 7, 8, 4, 8, 2, 5, 9, 9, 1 };
        int x = 10;
        // build dictionary
        Dictionary<int,int> dict = new   Dictionary<int,int>();
        for(int i=0; i< array.Length; i+=1){
            if(dict.ContainsKey(array[i])){
                dict[array[i]] += 1;
            } else {
                dict.Add(array[i], 1);
            }
        }
        // using dictionary
        for(int i=0; i< array.Length; i+=1){
            if(dict.ContainsKey(x - array[i])) {
                int count = dict[x - array[i]];
                if(x - array[i] == array[i]){
                    count -= 1;
                }

                for(int j = 0; j< count; j+=1 ) {
                    Console.Write("(" + array[i] + "," + (x - array[i]) + ")");
                }

                dict[array[i]] -=1;
                if(dict[array[i]] == 0){
                    dict.Remove(array[i]);
                }
            }
        }
        Console.WriteLine();
    }
}