Dadas dos arrays nums[] de tamaño N y target[] . La tarea es encontrar el número de subarreglos no vacíos de nums[] que no contienen todos los números en target[] . Como la respuesta puede ser muy grande, calcule el resultado módulo 10 9 +7 .
Ejemplos:
Entrada: nums = {1, 2, 2}, objetivo = {1, 2}
Salida: 4
Explicación: Los subarreglos que no contienen ni 1 ni 2 en nums[] son:
{1}, {2}, { 2}, {2, 2}Entrada: nums = {1, 2, 3}, target = {1}
Salida: 3
Explicación: Los subarreglos son {2}, {3}, {2, 3}.
Enfoque: El enfoque simple para resolver este problema se basa en la siguiente idea:
- Encuentre el número de subarreglos que contienen todos los elementos del arreglo target[] .
- Si hay X tales subarreglos, entonces el número de subarreglos que no contienen todos los elementos será [N*(N+1)/2 – X], donde N*(N+1)/2 es el número total de subarreglos de array números[] .
- Aquí use el concepto de dos punteros para encontrar el número X y obtener el resultado deseado usando la fórmula anterior.
Siga los pasos que se mencionan a continuación:
- Mantenga todos los números en un conjunto desordenado y mantenga el conteo de frecuencia de todos estos números en un mapa .
- Ahora use el enfoque de dos punteros con un puntero izquierdo y uno derecho .
- Avance el extremo derecho hasta que todos los números del objetivo se encuentren en esa ventana.
- Una vez que lo hagamos, cuente cuántos subarreglos comienzan a la izquierda que contienen cada número en el objetivo y avancen a la izquierda hasta que ya no haya todos los elementos del objetivo[] .
- Siga restando el subarreglo que contiene cada número en el objetivo del subarreglo total, lo que dará la respuesta final requerida.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
// Function to count subarrays that
// do not contain target array
int countSubarrays(vector<int>& nums,
vector<int>& target)
{
// Size of nums
int N = nums.size();
// The total number of subarrays in nums[]
long long ans = N * (N + 1LL) / 2;
// Map to store frequency
unordered_map<int, int> freq;
unordered_set<int> active(target.begin(),
target.end());
// Left pointer as mentioned above
int left = 0;
// Right pointer loop until all elements
// in target are present
for (int right = 0; right < N; right++)
{
// Populating the frequency
// of elements in freq map
if (active.count(nums[right]))
freq[nums[right]]++;
// When there is the possibility
// that it contains the subarray
// target then only target and
// freq size will be equal
while (freq.size() == target.size()) {
// Total subarray-count of
// subarray which contains
// target = Count of
// subarray which does not
// contain target which is
// our required ans
ans -= (N - right);
if (active.count(nums[left])) {
if (--freq[nums[left]] == 0)
// erasing element
// frequency from left
// pointer
freq.erase(nums[left]);
}
// Advance the left pointer
// until we no longer have
// every number in target
left++;
}
}
// Returning ans mod 10^9+7
return ans % MOD;
}
// Driver code
int main()
{
vector<int> nums = { 1, 2, 2 };
vector<int> target = { 1, 2 };
// Function call
cout << countSubarrays(nums, target);
return 0;
}
Java
// Java code to implement the approach
import java.util.*;
class GFG{
static int MOD = 1000000007;
// Function to count subarrays that
// do not contain target array
static int countSubarrays(Integer[]nums,
Integer[] target)
{
// Size of nums
int N = nums.length;
// The total number of subarrays in nums[]
long ans = N * (N + 1) / 2;
// Map to store frequency
HashMap<Integer,Integer> freq = new HashMap<Integer,Integer> ();
HashSet<Integer> active = new HashSet<Integer>();
active.addAll(Arrays.asList(target));
// Left pointer as mentioned above
int left = 0;
// Right pointer loop until all elements
// in target are present
for (int right = 0; right < N; right++)
{
// Populating the frequency
// of elements in freq map
if (active.contains(nums[right]))
if(freq.containsKey(nums[right])){
freq.put(nums[right], freq.get(nums[right])+1);
}
else{
freq.put(nums[right], 1);
}
// When there is the possibility
// that it contains the subarray
// target then only target and
// freq size will be equal
while (freq.size() == target.length) {
// Total subarray-count of
// subarray which contains
// target = Count of
// subarray which does not
// contain target which is
// our required ans
ans -= (N - right);
if (active.contains(nums[left])) {
if (freq.get(nums[left])-1 == 0)
// erasing element
// frequency from left
// pointer
freq.remove(nums[left]);
}
// Advance the left pointer
// until we no longer have
// every number in target
left++;
}
}
// Returning ans mod 10^9+7
return (int) (ans % MOD);
}
// Driver code
public static void main(String[] args)
{
Integer[] nums = { 1, 2, 2 };
Integer[] target = { 1, 2 };
// Function call
System.out.print(countSubarrays(nums, target));
}
}
// This code is contributed by 29AjayKumar
Python3
# python3 code to implement the approach
MOD = 1000000007
# Function to count subarrays that
# do not contain target array
def countSubarrays(nums, target) :
# Size of nums
N = len(nums)
# The total number of subarrays in nums[]
ans = N * (N + 1) // 2
# Map to store frequency
freq = {}
active = set(target)
# Left pointer as mentioned above
left = 0
# Right pointer loop until all elements
# in target are present
for right in range(0, N) :
# Populating the frequency
# of elements in freq map
if ( nums[right] in active) :
freq[nums[right]] = freq[nums[right]] + 1 if nums[right] in freq else 1
# When there is the possibility
# that it contains the subarray
# target then only target and
# freq size will be equal
while ( len(freq) == len(target)) :
# Total subarray-count of
# subarray which contains
# target = Count of
# subarray which does not
# contain target which is
# our required ans
ans -= (N - right)
if ( nums[left] in active) :
if ( nums[left] in freq ) :
# erasing element
# frequency from left
# pointer
if freq[nums[left]] == 1 :
del freq[nums[left]]
else :
freq[nums[left]] -= 1
# Advance the left pointer
# until we no longer have
# every number in target
left += 1
# Returning ans mod 10^9+7
return ans % MOD
# Driver code
if __name__ == "__main__" :
nums = [ 1, 2, 2 ]
target = [ 1, 2 ]
# Function call
print(countSubarrays(nums, target))
# This code is contributed by rakeshsahni
C#
// C# program to implement above approach
using System;
using System.Collections.Generic;
class GFG
{
public static int MOD = 1000000007;
// Function to count subarrays that
// do not contain target array
public static int countSubarrays(List<int> nums, List<int> target)
{
// Size of nums
int N = nums.Count;
// The total number of subarrays in nums[]
long ans = ((long)N * (long)(N + 1))/2;
// Map to store frequency
Dictionary<int, int> freq = new Dictionary<int, int>();
HashSet<int> active = new HashSet<int>(target);
// Left pointer as mentioned above
int left = 0;
// Right pointer loop until all elements
// in target are present
for (int right = 0; right < N; right++)
{
// Populating the frequency
// of elements in freq map
if (active.Contains(nums[right])){
int val;
if (freq.TryGetValue(nums[right], out val))
{
// yay, value exists!
freq[nums[right]] = val + 1;
}
else
{
// darn, lets add the value
freq.Add(nums[right], 1);
}
}
// When there is the possibility
// that it contains the subarray
// target then only target and
// freq size will be equal
while (freq.Count == target.Count) {
// Total subarray-count of
// subarray which contains
// target = Count of
// subarray which does not
// contain target which is
// our required ans
ans -= (N - right);
if (active.Contains(nums[left])) {
--freq[nums[left]];
if (freq[nums[left]] == 0){
// erasing element
// frequency from left
// pointer
freq.Remove(nums[left]);
}
}
// Advance the left pointer
// until we no longer have
// every number in target
left++;
}
}
// Returning ans mod 10^9+7
return (int)(ans % MOD);
}
// Driver Code
public static void Main(string[] args)
{
// Input Array
List<int> nums = new List<int>{
1, 2, 2
};
List<int> target = new List<int>{
1, 2
};
// Function call and printing result.
Console.Write(countSubarrays(nums, target));
}
}
// This code is contributed by subhamgoyal2014.
Javascript
<script>
// JavaScript code to implement the approach
const MOD = 1000000007
// Function to count subarrays that
// do not contain target array
function countSubarrays(nums, target){
// Size of nums
let N = nums.length
// The total number of subarrays in nums[]
let ans =Math.floor(N * (N + 1) / 2)
// Map to store frequency
let freq = new Map()
let active = new Set()
for(let i of target){
active.add(i)
}
// Left pointer as mentioned above
let left = 0
// Right pointer loop until all elements
// in target are present
for(let right=0;right<N;right++){
// Populating the frequency
// of elements in freq map
if (active.has(nums[right])){
freq.set(nums[right], freq.has(nums[right])?freq[nums[right]] + 1:1)
}
// When there is the possibility
// that it contains the subarray
// target then only target and
// freq size will be equal
while (freq.size == target.length){
// Total subarray-count of
// subarray which contains
// target = Count of
// subarray which does not
// contain target which is
// our required ans
ans -= (N - right)
if (active.has(nums[left])){
if (freq.has(nums[left])){
// erasing element
// frequency from left
// pointer
if(freq.get(nums[left]) == 1)
freq.delete(nums[left])
else
freq.set(nums[left], freq.get(nums[left])- 1)
}
}
// Advance the left pointer
// until we no longer have
// every number in target
left += 1
}
}
// Returning ans mod 10^9+7
return ans % MOD
}
// Driver code
let nums = [ 1, 2, 2 ]
let target = [ 1, 2 ]
// Function call
document.write(countSubarrays(nums, target),"</br>")
// This code is contributed by shinjanpatra
<script>
Producción
4
Tiempo Complejidad: 
Espacio Auxiliar: 