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

Question

我正在做一项作业，我必须找到总计为 "x" 且具有 average/best O(n) 或线性运行时复杂度的数字对。我不能使用蛮力，因为它会增加复杂性。

我正在使用 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();
    }
}

Answer 2

这是我使用字典的简单解决方案。 O(n) 次。

namespace TwoSumLeetCode
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] arr = { 1, 2, 7, 9, 4 };

            int target = 13;

            Console.WriteLine(TwoSum(arr, target));

            Console.ReadLine();
        }

        // assuming array and target are provided.
        public static int[] TwoSum(int[] nums, int target)
        {
            Dictionary<int, int> dict = new Dictionary<int, int>();
            for (int i = 0; i < nums.Length(); ++i)
            {
                if (dict.ContainsKey(target - nums[i]))
                {
                    return new int[] { dict[target - nums[i]], i };
                }

                else
                {
                    dict[nums[i]] = i;
                }
            }

            return null;
        }
    }
}

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

Two Sum Problem with HashSet not working with duplicates

c#

algorithm

big-o

hashset