Continuous Subarray SUm

523.Continuous Subarray Sum

Array

Hash Table

Prefix Sum

Problem Statement:

Given an integer array nums and an integer k, return true if nums has a continuous subarray of size at least 2 that sums up to a multiple of k, or false otherwise.

Example:

Input:

nums = [23,2,4,6,7], k = 6

→

Output:

true

Java Solution:

// Follow up: If K is zero, don't modulo!
public boolean checkSubarraySum(int[] nums, int k) {
    int sum = 0;
    Map<Integer, Integer> map = new HashMap<>();
    map.put(0, -1);  // Initialize with 0 sum at index -1
    
    for (int i = 0; i < nums.length; i++) {
        sum += nums[i];

        // Check if current sum remainder exists
        if (map.containsKey(sum %= k)) {
            if (i - map.get(sum) >= 2) return true;  // Verify length >= 2
        } else {
            map.put(sum, i);  // Store first occurrence of this remainder
        }
    }
    
    return false;
}

Python Solution:

def checkSubarraySum(self, nums: List[int], k: int) -> bool:
    sum_map = {0: -1}  # Initialize with 0 sum at index -1
    curr_sum = 0
    
    for i, num in enumerate(nums):
        curr_sum += num
        
        if k != 0:  # Handle k = 0 case
            curr_sum = curr_sum % k
            
        if curr_sum in sum_map:
            if i - sum_map[curr_sum] >= 2:
                return True
        else:
            sum_map[curr_sum] = i
            
    return False

C++ Solution:

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> sum_map;
        sum_map[0] = -1;
        int curr_sum = 0;
        
        for(int i = 0; i < nums.size(); i++) {
            curr_sum += nums[i];
            
            if(k != 0)  // Handle k = 0 case
                curr_sum %= k;
                
            if(sum_map.count(curr_sum)) {
                if(i - sum_map[curr_sum] >= 2)
                    return true;
            }
            else {
                sum_map[curr_sum] = i;
            }
        }
        
        return false;
    }
};

Complexity:

Time: O(n) | Space: O(min(n,k)) where n is array length