arrays - 创建逻辑，将 arrAY 中的每个元素与 ArrAY 中的每个元素相加，并在总和为零时输出这两项的索引

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) 中进行查找。