Leetcode # 2799. Count Complete Subarrays in an Array

https://leetcode.com/contest/weekly-contest-356/problems/count-complete-subarrays-in-an-array/

Solution

Time Complexity: O(len(nums))
Space Complexity: O(len(nums))
(The input and output generally do not count towards the space complexity.)

class Solution:
  def countCompleteSubarrays(self, nums: List[int]) -> int:
    counter = set(nums)
    dp = [set([num]) for num in nums]
    subarrays_n = [len(_dp) == len(counter) for _dp in dp].count(True)
    for i in range(1, len(nums)):
      for j in range(len(dp[i:])):
        dp[i + j].add(nums[j])
        if len(dp[i + j]) == len(counter):
          subarrays_n += 1
    return subarrays_n

用 template 格式重寫

class Solution:
  def countCompleteSubarrays(self, nums: List[int]) -> int:
    counter = set(nums)
    dp = [set([num]) for num in nums]
    subarrays_n = [len(_dp) == len(counter) for _dp in dp].count(True)
    for l in range(1, len(nums)):
      for i in range(len(nums) - l):
        dp[i].add(nums[i + l])
        if len(dp[i]) == len(counter):
          subarrays_n += 1
    return subarrays_n

Last Updated on 2023/08/16 by A1go