Общий префикс без учета кратности

средне

# решено

Даны два массива целых чисел nums1 и nums2 одинаковой длины. Для каждого префикса нужно посчитать число общих элементов без учета кратности.

"Без учета кратности" - это значит, что присутствие одного и того же числа в префиксах считается только один раз независимо от количества повторов.

Пример 1:

Ввод: nums1 = [2,2,3,4], nums2 = [3,2,4,2]
Вывод: [0,1,2,3]
Объяснение:
0 = [2] и [3] имеют 0 общих элементов
1 = [2,2] и [3,2] имеют 1 общий элемент (2)
2 = [2,2,3] и [3,2,4] имеют 2 общих элемента (2,3)
3 = [2,2,3,4] и [3,2,4,2] имеют 3 общих элемента (2,3,4)
(0,1,2,3)

Пример 2:

Ввод: nums1 = [3,2,2], nums2 = [2,1,2]
Вывод: [0,1,1]

Ограничения:

len(nums1) = len(nums2)
len(nums1) >= 1
len(nums2) >= 1

public class Solution {
    public static List<int> FindCommonPrefix(List<int> nums1, List<int> nums2) {
        HashSet<int> used1 = new HashSet<int>();
        HashSet<int> used2 = new HashSet<int>();
        int commonCount = 0;
        List<int> result = new List<int>();

        for (int i = 0; i < nums1.Count; i++) {
            // новый элемент из nums1
            if (!used1.Contains(nums1[i])) {
                used1.Add(nums1[i]);
                if (used2.Contains(nums1[i])) {
                    commonCount++;
                }
            }

            // новый элемент из nums2
            if (!used2.Contains(nums2[i])) {
                used2.Add(nums2[i]);
                if (used1.Contains(nums2[i])) {
                    commonCount++;
                }
            }
            result.Add(commonCount);
        }
        return result;
    }
}

#include <vector>
#include <unordered_set>

using namespace std;

vector<int> findCommonPrefix(vector<int> nums1, vector<int> nums2) {
    unordered_set<int> used1;
    unordered_set<int> used2;
    int commonCount = 0;
    vector<int> result;

    for (size_t i = 0; i < nums1.size(); ++i) {
        // новый элемент из nums1
        if (used1.find(nums1[i]) == used1.end()) {
            used1.insert(nums1[i]);
            if (used2.find(nums1[i]) != used2.end()) {
                ++commonCount;
            }
        }

        // новый элемент из nums2
        if (used2.find(nums2[i]) == used2.end()) {
            used2.insert(nums2[i]);
            if (used1.find(nums2[i]) != used1.end()) {
                ++commonCount;
            }
        }
        result.push_back(commonCount);
    }
    return result;
}

package main

func findCommonPrefix(nums1 []int, nums2 []int) []int {
    used1 := make(map[int]bool)
    used2 := make(map[int]bool)
    commonCount := 0
    result := make([]int, len(nums1))

    for i := 0; i < len(nums1); i++ {
        // новый элемент из nums1
        if !used1[nums1[i]] {
            used1[nums1[i]] = true
            if used2[nums1[i]] {
                commonCount++
            }
        }

        // новый элемент из nums2
        if !used2[nums2[i]] {
            used2[nums2[i]] = true
            if used1[nums2[i]] {
                commonCount++
            }
        }
        result[i] = commonCount
    }
    return result
}

import java.util.*;

public class Solution {
    public List<Integer> findCommonPrefix(List<Integer> nums1, List<Integer> nums2) {
        Set<Integer> used1 = new HashSet<>();
        Set<Integer> used2 = new HashSet<>();
        int commonCount = 0;
        List<Integer> result = new ArrayList<>();

        for (int i = 0; i < nums1.size(); i++) {
            // новый элемент из nums1
            if (!used1.contains(nums1.get(i))) {
                used1.add(nums1.get(i));
                if (used2.contains(nums1.get(i))) {
                    commonCount++;
                }
            }

            // новый элемент из nums2
            if (!used2.contains(nums2.get(i))) {
                used2.add(nums2.get(i));
                if (used1.contains(nums2.get(i))) {
                    commonCount++;
                }
            }
            result.add(commonCount);
        }
        return result;
    }
}

from typing import List

def find_common_prefix(nums1: List[int], nums2: List[int]) -> List[int]:
    used1 = set()
    used2 = set()
    common_count = 0
    result = []

    for i in range(len(nums1)):
        # новый элемент из nums1
        if nums1[i] not in used1:
            used1.add(nums1[i])
            if nums1[i] in used2:
                common_count += 1

        # новый элемент из nums2
        if nums2[i] not in used2:
            used2.add(nums2[i])
            if nums2[i] in used1:
                common_count += 1
        result.append(common_count)
    return result

/**
* @param {number[]} nums1
* @param {number[]} nums2
* @returns {number[]}
*/
export function findCommonPrefix(nums1, nums2) {
  const used1 = new Set();
  const used2 = new Set();
  let commonCount = 0;
  const result = [];

  for (let i = 0; i < nums1.length; i++) {
    // новый элемент из nums1
    if (!used1.has(nums1[i])) {
      used1.add(nums1[i]);
      if (used2.has(nums1[i])) {
        commonCount += 1;
      }
    }

    // новый элемент из nums2
    if (!used2.has(nums2[i])) {
      used2.add(nums2[i]);
      if (used1.has(nums2[i])) {
        commonCount += 1;
      }
    }
    result.push(commonCount);
  }
  return result;
}

Оценка сложности

Время: O(n), где n - размер nums1 и nums2
Память: O(n)