Skip to content

454. 4Sum II 👍

  • Time: $O(n^2)$
  • Space: $O(n^2)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
 public:
  int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3,
                   vector<int>& nums4) {
    int ans = 0;
    unordered_map<int, int> count;

    for (const int a : nums1)
      for (const int b : nums2)
        ++count[a + b];

    for (const int c : nums3)
      for (const int d : nums4)
        if (const auto it = count.find(-c - d); it != count.cend())
          ans += it->second;

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
  public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
    int ans = 0;
    Map<Integer, Integer> count = new HashMap<>();

    for (final int a : nums1)
      for (final int b : nums2)
        count.merge(a + b, 1, Integer::sum);

    for (final int c : nums3)
      for (final int d : nums4)
        if (count.containsKey(-c - d))
          ans += count.get(-c - d);

    return ans;
  }
}

1
2
3
4
5
class Solution:
  def fourSumCount(self, nums1: list[int], nums2: list[int],
                   nums3: list[int], nums4: list[int]) -> int:
    count = collections.Counter(a + b for a in nums1 for b in nums2)
    return sum(count[-c - d] for c in nums3 for d in nums4)