Algorithm
Problem Name: 523. Continuous Subarray Sum
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
xis a multiple ofkif there exists an integernsuch thatx = n * k.0is always a multiple ofk.
Example 1:
Input: nums = [23,2,4,6,7], k = 6 Output: true Explanation: [2, 4] is a continuous subarray of size 2 whose elements sum up to 6.
Example 2:
Input: nums = [23,2,6,4,7], k = 6 Output: true Explanation: [23, 2, 6, 4, 7] is an continuous subarray of size 5 whose elements sum up to 42. 42 is a multiple of 6 because 42 = 7 * 6 and 7 is an integer.
Example 3:
Input: nums = [23,2,6,4,7], k = 13 Output: false
Constraints:
1 <= nums.length <= 1050 <= nums[i] <= 1090 <= sum(nums[i]) <= 231 - 11 <= k <= 231 - 1
Code Examples
#1 Code Example with C Programming
Code -
C Programming
typedef struct e_s {
int mod;
int idx;
struct e_s *shadow;
} e_t;
#define SZ 1024
e_t *lookup(e_t **set, int mod) {
e_t *e = set[mod % SZ];
while (e && e->mod != mod) {
e = e->shadow;
}
return e;
}
void put(e_t **set, e_t *e, int mod, int idx) {
e->mod = mod;
e->idx = idx;
e->shadow = set[mod % SZ];
set[mod % SZ] = e;
}
bool checkSubarraySum(int* nums, int numsSize, int k) {
int i, s, found = 0;
e_t buff[10000];
int n;
e_t *set[SZ] = { 0 }, *e;
put(set, &buff[n ++], 0, -1);
s = 0;
for (i = 0; i < numsSize; i ++) {
s += nums[i];
if (k) s = s % k;
e = lookup(set, s);
if (e) {
if (i - e->idx >= 2) {
found = 1;
break;
}
} else {
put(set, &buff[n ++], s, i);
}
}
return found;
}
Input
nums = [23,2,4,6,7], k = 6
Output
true
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
bool checkSubarraySum(vector<int>& nums, int k) {
unordered_map < int, int>m;
k = abs(k);
int sum = 0;
for(int i = 0; i < nums.size(); i++){
sum += nums[i];
if(i < nums.size() - 1 && nums[i] == 0 && nums[i + 1] == 0> return true;
if(k != 0 && sum % k == 0 && i > 0) return true;
for(int j = 0; k != 0 && j*k < sum; j++)
if(m.count(sum - j*k> > 0 && i - m[sum - j*k] > 0) return true;
m[sum] = i;
}
return false;
}
};
Input
nums = [23,2,4,6,7], k = 6
Output
true
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public boolean checkSubarraySum(int[] nums, int k) {
Map map = new HashMap<>();
map.put(0, -1);
int currSum = 0;
for (int i = 0; i < nums.length; i++) {
currSum += nums[i];
int rem = currSum % k;
if (map.containsKey(rem)) {
if (i - map.get(rem) >= 2) {
return true;
}
} else {
map.put(rem, i);
}
}
return false;
}
}
Input
nums = [23,2,6,4,7], k = 6
Output
true
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const checkSubarraySum = function(nums, k) {
const map = {0: -1}
let runningSum = 0
for(let i = 0; i < nums.length; i++) {
runningSum += nums[i]
if(k !== 0) runningSum %= k
let prev = map[runningSum]
if(prev != null) {
if(i - prev > 1) return true
} else {
map[runningSum] = i
}
}
return false
};
Input
nums = [23,2,6,4,7], k = 6
Output
true
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def checkSubarraySum(self, nums, k):
if not k: return any(nums[i] == nums[i - 1] == 0 for i in range(1, len(nums)))
mods, sm = set(), 0
for i, num in enumerate(nums):
sm = (sm + num) % k
if (sm in mods and num or (i and not nums[i - 1])) or (not sm and i): return True
mods |= {sm}
return False
Input
nums = [23,2,6,4,7], k = 13
Output
false
#6 Code Example with C# Programming
Code -
C# Programming
using System.Collections.Generic;
namespace LeetCode
{
public class _0523_ContinuousSubarraySum
{
public bool CheckSubarraySum(int[] nums, int k)
{
var map = new Dictionary < int, int>();
map.Add(0, -1);
var sum = 0;
for (int i = 0; i < nums.Length; i++)
{
sum += nums[i];
if (k != 0)
sum %= k;
if (map.ContainsKey(sum))
{
if (i - map[sum] >= 2)
return true;
}
else
map[sum] = i;
}
return false;
}
}
}
Input
nums = [23,2,6,4,7], k = 13
Output
false