Leetcode Continuous Subarray Sum problem solution

by

In this Leetcode Continuous Subarray Sum problem solution we have 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.

Leetcode Continuous Subarray Sum problem solution

Problem solution in Python.

class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        lookup = {0:-1}
        curr_sum = 0
        
        for i, n in enumerate(nums):
            if k != 0:
                curr_sum = (curr_sum + n) % k
            else:
                curr_sum += n
            if curr_sum not in lookup:
                lookup[curr_sum] = i
            else:
                if i - lookup[curr_sum] >= 2:
                    return True
        return False

Problem solution in Java.

class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        
        HashMap<Integer, Integer> map = new HashMap<>();
        
        map.put(0,0);
        
        int sum = 0;
        
        for(int i=0; i<nums.length; i++){
            
            sum += nums[i];
            
            if(!map.containsKey(sum % k)){
                map.put(sum % k, i + 1);
            }else{
                if(map.get(sum % k) < i){
                    return true;
                }
            }
            
        }
        
        return false;
        
    }
}

Problem solution in C++.

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        unordered_map<int,int>m;
        m[0] = -1;
        int sum = 0;

        for(int i = 0;i < nums.size();i++){
            sum += nums[i];
            if(k != 0){
                sum %= k;
            }

            if(m.count(sum) > 0){
                if(i - m[sum] > 1) return true;
            }
            else{
                m[sum] = i;
            }

        }
        return false;
    }
};

Problem solution in C.

bool checkSubarraySum(int* nums, int numsSize, int k){
    if (numsSize == 1) return false;
    else if (k == 1) return true;
    
    bool *map = calloc(k, sizeof(bool)); 
    // using bool-type would save u some memory
    int sum = 0;    

    for(int i = 0; i < numsSize; i++){
        if (nums[i] % k == 0){  
            // return true if encounter at least two conterminous k's multiple
            // else we do not do any hashing
            if (i < numsSize-1 && nums[i+1] % k == 0) return true;
            else continue;
        }
        sum += nums[i]; // accumulate the array
        if (sum % k == 0) return true;
        else if (map[sum % k] > 0) return true;
        map[sum % k] = 1;
    }

    return false;
}