time-complexity - 给定 2 个数组的分数求和 - O(n)？

Question

你有 2 个 int 数组。

                    A=[1,   2,   1]
                    B=[2,   3,   3]

    so fractions are: 1/2, 2/3,  1/3

A是分子，B是分母。所以分数是:1/2、2/3、1/3

找出所有总和为 1 的对。

示例:这里有 2/3 + 1/3 = 1，所以计数 = 1

返回 1

返回模 10^9 +7，因为输入可能很大

我在 O(n^2) 中完成了它，通过它一次，然后计算 2 的加法并检查它是否为 1 并更新计数器。

在 O(n) 中是可能的吗？

任何语言 idm 示例:

  function solution(integer array A, integer array B){
    return integer_counter;
  }

Answer 1

这是一个使用字典的 C# 解决方案

public static int SumOfFraction(int[] numerator, int[] denominator) {
  int count = 0;
  Dictionary < int, List < int >> keyValuePairs = new Dictionary < int, List < int >> ();

  for (int i = 0; i < denominator.Length; i++) {
    if (keyValuePairs.ContainsKey(denominator[i])) {
      keyValuePairs[denominator[i]].Add(numerator[i]);
    } else {
      keyValuePairs.Add(denominator[i], new List < int > {
        numerator[i]
      });
    }
  }

  foreach(var keypair in keyValuePairs) {
    if (keypair.Key == keypair.Value.Sum()) {
      count++;
    }
  }

  return count;
}