aboutsummaryrefslogtreecommitdiff
path: root/continuous_subarray.py
blob: 7e0505f5c48a5d30c7d72095edb5015aecfb842d (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# 2762. Continuous Subarrays

"""
you are given a 0-indexed integer array 'nums'. a subarray of 'nums' is
called continuous if: let 'i', 'i + 1', ..., 'j' be the indices in the
subarray. then, for each pair of indices 'i <= i_1, i_2 <= j', '0 <= |
nums[i_1] - nums[i_2]| <= 2'. return the total number of continuous
subarrays. a subarray is a contiguous non-empty sequence of elements within
an array
"""


class Solution(object):
    def continuousSubarrays(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        i, ans, d = 0, 0, dict()
        for j, n in enumerate(nums):
            t = d.copy()
            for k, v in t.items():
                if abs(k - n) > 2:
                    i = max(i, v + 1)
                    d.pop(k)
            d[n] = j
            ans += j - i + 1
        return ans


if __name__ == "__main__":
    obj = Solution()
    print(obj.continuousSubarrays(nums=[5, 4, 2, 4]))
    print(obj.continuousSubarrays(nums=[1, 2, 3]))