Leetcode # 523. Continuous Subarray Sum

Problem

https://leetcode.com/problems/continuous-subarray-sum/

First Try
[Time Limit Exceeded  81 / 99 testcases passed]

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

Ver. 1

class Solution:
  def checkSubarraySum(self, nums: List[int], k: int) -> bool:
    if len(nums) < 2: return False

    def _check_sub_array_sum(nums, k, sub_sum):
      if len(nums) < 2:    return False
      if sub_sum % k == 0: return True

      result =  _check_sub_array_sum(nums[1:], k, sub_sum - nums[0]) \
                or _check_sub_array_sum(nums[:-1], k, sub_sum - nums[-1])
      return result

    sub_sum = sum(nums)
    return _check_sub_array_sum(nums, k, sub_sum)

Ver. 2: Memoization

class Solution:
  def checkSubarraySum(self, nums: List[int], k: int) -> bool:
    if len(nums) < 2: return False
    start_n_end = {}

    def _check_sub_array_sum(nums, k, sub_sum, start, end):
      nonlocal start_n_end
      if len(nums) < 2:    return False
      if sub_sum % k == 0: return True
      _range = (start, end)
      if _range in start_n_end: return start_n_end[_range]

      result =  _check_sub_array_sum(nums[1:], k, sub_sum - nums[0], (start + 1), end) \
                or _check_sub_array_sum(nums[:-1], k, sub_sum - nums[-1], start, (end - 1))
      start_n_end[_range] = result
      return result

    sub_sum = sum(nums)
    return _check_sub_array_sum(nums, k, sub_sum, 0, len(nums) - 1)

Solution: Prefix Sum + Hash Table

相關例題

• Leetcode # 974. ⭐️ Subarray Sums Divisible by K

Algorithm

• k = 5
• nums = 
  

  1

  5

  2

  1

  5

  2

  1

  3

• $$ prefix\_sum[i] := \sum^{i – 1}_{k = 0}{num[k]} $$
  prefix_sum = 

  0

  1

  6

  8

  9

  14

  16

  17

  20

• prefix_mod := prefix_sum % k =
  

  0

  1

  1

  3

  4

  4

  1

  2

  0

  prefix_mod[x] = a ⇒sum(nums[:x]) = n * k + a
  if ∃ y ≤ x – 2 s.t. prefix_mod[y] = a ⇒ nums[y:x] is a good sub array

  • length = 2 – 1 = 1 < 2
    

    1

    1

  • length = 2 – 1 = 1 < 2
    

    4

    4

  • sum[2:6] = [2, 1, 5, 2, 1]; sum[1:6] = [5, 2, 1, 5, 2, 1]; sum[0:8] = [1, 5, 2, 1, 5, 2, 1]
    

    1

    3

    4

    4

    1

    1

    1

    3

    4

    4

    1

    0

    1

    1

    3

    4

    4

    1

    2

    0

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 checkSubarraySum(self, nums: List[int], k: int) -> bool:
    prefix_sum = [0] * (len(nums) + 1)
    for i in range(1, len(nums) + 1):
      prefix_sum[i] = prefix_sum[i - 1] + nums[i - 1]
    m_seen = defaultdict(list)
    for x, psum in enumerate(prefix_sum):
      m = psum % k
      if m in m_seen:
        for y in m_seen[m]:
          if x - y >= 2: return True
      m_seen[m].append(x)
    return False

Last Updated on 2024/06/09 by A1go