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.
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; }