Last updated on February 2nd, 2025 at 05:20 am

Here, we see the Continuous Subarray Sum LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Dynamic Programming, Math

Companies

Facebook

Level of Question

Medium

Continuous Subarray Sum LeetCode Solution

1. Problem Statement

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.

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

2. Coding Pattern Used in Solution

The coding pattern used in this code is “Prefix Sum with Hashing”. This pattern is commonly used to solve problems involving subarrays or subsequences where you need to efficiently check for specific properties (e.g., sum, modulo, etc.) using cumulative sums and hash maps for quick lookups.

3. Code Implementation in Different Languages

3.1 Continuous Subarray Sum C++

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        if(nums.size()<2)
            return false;
        unordered_map<int, int> mp;
        mp[0]=-1;
        int runningSum=0;
        for(int i=0;i<nums.size();i++)
        {
            runningSum+=nums[i];
            if(k!=0) 
                runningSum = runningSum%k;
            if(mp.find(runningSum)!=mp.end())
            {
                if(i-mp[runningSum]>1)
                    return true;
            }
            else
            {
                mp[runningSum]=i;
            }       
        }
        return false;
    }
};

3.2 Continuous Subarray Sum Java

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

3.3 Continuous Subarray Sum JavaScript

var checkSubarraySum = function (nums, k) {
	let sum = 0
	let prefix = 0;
	const hash = new Set();
	for (let i = 0; i < nums.length; i++) {
		sum += nums[i]
		if (k != 0) sum %= k
		if(hash.has(sum)) return true
		hash.add(prefix);
		prefix = sum;
	}
	return false
};

3.4 Continuous Subarray Sum Python

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

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(N)	O(N)
Java	O(N)	O(N)
JavaScript	O(N)	O(N)
Python	O(N)	O(N)

where, N is the size of the input array nums.