title: Count the number of sub arrays such that each element in the subarray appears at least twice
body: <p>I have come across a problem and can't seem to come up with an efficient solution. The problem is as follows:</p>
  <p>Given an array A, count the number of consecutive contiguous subarrays such that each element in the subarray appears at least twice.</p>
  <p>Ex, for:</p>
  <pre><code>A = [0,0,0]
  </code></pre>
  <p>The answer should be 3 because we have</p>
  <pre><code>A[0..1] = [0,0]
  A[1..2] = [0,0]
  A[0..3] = [0,0,0]
  </code></pre>
  <p>Another example:</p>
  <pre><code>A=[1,2,1,2,3]
  </code></pre>
  <p>The answer should be 1 because we have:</p>
  <pre><code>A[0..3] = [1,2,1,2]
  </code></pre>
  <p>I can't seem to come up with an efficient solution for this algorithm. I have an algorithm that checks every possible subarray (O(n^2)), but I need something better. This is my naive solution:</p>
  <pre><code>def duplicatesOnSegment(arr):
      total = 0
      for i in range(0,len(arr)):
          unique = 0
          test = {}
          for j in range(i,len(arr)):
              k = arr[j]
              if k not in test:
                  test[k] = 1
              else:
                  test[k] +=  1
  
              if test[k] == 1:
                  unique += 1
              elif test[k] == 2:
                  unique -= 1
              if unique == 0:
                  total += 1
      return total
  </code></pre>