I met this question in a simulation test. I have an O(n^2) solution but reveive time limit exceed error. What would be a better solution?
Given an array A, count the number of consecutive contiguous subarrays such that each element in the subarray appears at least twice.
Ex, for:
A = [0,0,0]
The answer should be 3 because we have
A[0..1] = [0,0]
A[1..2] = [0,0]
A[0..3] = [0,0,0]
Another example:
A=[1,2,1,2,3]
The answer should be 1 because we have:
A[0..3] = [1,2,1,2]
My solution(time limit exceeded):
import collections
def subarray_with_notUnique_element(arr):
ans=0
for i in range(len(arr)):
d=collections.defaultdict(int)
count=0
for j in range(i,len(arr)):
d[arr[j]]+=1
#if an element is unique
if d[arr[j]]==1:
count+=1
elif d[arr[j]]==2:
count-=1
#if no element is unqie, increase ans
if count==0:
ans+=1
return ansHow to make it faster?