Leetcode Continuous Subarray Sum problem solution

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 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

Continuous Subarray Sum 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;
}

Leetcode Continuous Subarray Sum problem solution

Leetcode Continuous Subarray Sum problem solution in Python.

Continuous Subarray Sum problem solution in Java.

Problem solution in C++.

Problem solution in C.

Leave a Reply

Pages

Practice