523. Continuous Subarray Sum

Problem Statement

link: LeetCode.cn LeetCode Given an integer array nums and an integer k, return true if nums has a good subarray or false otherwise.

A good subarray is a subarray where:

its length is at least two, and the sum of the elements of the subarray is a multiple of k. Note that:

A subarray is a contiguous part of the array. An integer x is a multiple of k if there exists an integer n such that x = n * k. 0 is always a multiple of k.

Example:

Input: nums = [23,2,4,6,7], k = 6 Output: true

Input: nums = [23,2,6,4,7], k = 6 Output: true

Input: nums = [23,2,6,4,7], k = 13 Output: false

Constraints: 1 <= nums.length <= 105 0 <= nums[i] <= 109 0 <= sum(nums[i]) <= 231 - 1 1 <= k <= 231 - 1

Solution Approach

Use a prefix sum and modulo operation to track the remainder when the cumulative sum is divided by k, and utilize a hash table to detect if the same remainder has been seen before to determine if there exists a subarray with a sum that is a multiple of k.

Algorithm

1. Prefix Sum Calculation: Iterate through the array while maintaining a cumulative prefix sum. Compute the remainder of this prefix sum when divided by k.
2. Hash Table Tracking: Use a hash table to store the first occurrence of each remainder. Check if the current remainder has been seen before and ensure that the length of the subarray is at least two.
3. Remainder Comparison: If the same remainder is found in the hash table, and the subarray length is valid, return true. If not, update the hash table with the current remainder and continue.

Implement

    class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        pres = defaultdict(int)
        pre = 0
        for i, n in enumerate(nums):
            last = pre
            pre += n
            pre %= k
            if pre in pres:
                return True
            pres[last] = i
        return False
            

    
    

Twitter  facebook  Email