创建一个逻辑，将arrA的每个元素与ArrB的每个元素求和，并在它们的和为零时输出这两个项的索引

Question

在一次采访中，我被问到一个问题，但没有找到最理想的解决方案。如何改进此代码？

创建C#逻辑，该逻辑将对arrayA中的每个元素和ArrayB中的每一个元素求和，并在它们的和为零时输出这两个项的索引。

int[] arrayA = new int[] { 5, 7, 9, 7, 13 };
int[] arrayB = new int[] { 5, -7, 10, 7, 34, -5 };

所以第一个和将是5+5，它不是零，所以我们不输出任何东西。然后是5+(-7(，它也不是零
在某个时刻，您将得到
5+(-5(，它将为零，索引将为0.5，如下所示，作为输出的第一行
您的输出应显示：
0,5
1,1
3,1
因为这些索引的和将等于零。专注于最简单的解决方案

public class Program
{
public static void Main()
{
int[] arrayA = new int[] { 5, 7, 9, 7, 13 };
int[] arrayB = new int[] { 5, -7, 10, 7, 34, -5 };
for (int i = 0; i < arrayA.Length; i++)
{
for (int j = 0; j < arrayB.Length; j++)
{
var sum = arrayA[i] + arrayB[j];
if (sum == 0)
Console.WriteLine($"arrayA[{i}] + arrayB[{j}] = 0");
}
}
}
}

当前时间复杂度O(m*n(。

更新：

谢谢你，雷纳尔先生！新的时间复杂度O(m+n(
这里的C#代码：

private static void SolutionFast(int[] arrayA, int[] arrayB)
{
var dictB = ArrayToDict(arrayB);
var result = new List<KeyValuePair<int, int>>();
for (var idxA = 0; idxA < arrayA.Length; idxA++)
{
var val = -arrayA[idxA];
if (dictB.ContainsKey(val))
{
for (var idxB = 0; idxB < dictB[val].Count; idxB++)
{
result.Add(new KeyValuePair<int, int>(idxA, dictB[val][idxB]));
}
}
}
foreach (var elem in result)
{
Console.WriteLine($"{elem.Key}, {elem.Value}");
}
}
private static Dictionary<int, List<int>> ArrayToDict(int[] arr)
{
var dict = new Dictionary<int, List<int>>();
for (var i = 0; i < arr.Length; i++)
{
if (!dict.ContainsKey(arr[i]))
{
dict.Add(arr[i], new List<int> { i });
}
else
{
dict[arr[i]].Add(i);
}
}
return dict;
}

Answer 1

如果您使用字典，您可以将此时间降到O(m+n)。

首先，您需要创建一个字典，其键是数组B的元素，值是我们找到这些元素的索引集
在这个问题的例子中，我们有

dict = {
5: {0}, 7: {1, 3}, 9: {2}, 13: {4}
}

然后，您可以轻松地输出结果偶(伪代码(：

result = empty list
for idx_a from 0 to length(arrayA) - 1 do {
val = arrayA[idx_a]
if val is a key of dict then {
for idx_b in dict[val] do {
result.add((idx_a, idx_b))
}
}
}
return result

这可以在O'm+n)中运行，这要归功于字典和集合的实现，它们允许在O(1)中查找。