523. Continuous Subarray Sum LeetCode Solution

In this guide, you will get 523. Continuous Subarray Sum LeetCode Solution with the best time and space complexity. The solution to Continuous Subarray Sum problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Continuous Subarray Sum solution in C++
Continuous Subarray Sum solution in Java
Continuous Subarray Sum solution in Python
Additional Resources

523. Continuous Subarray Sum LeetCode Solution image

Problem Statement of 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 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

Constraints:

1 <= nums.length <= 105
0 <= nums[i] <= 109
0 <= sum(nums[i]) <= 231 – 1
1 <= k <= 231 – 1

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)

523. Continuous Subarray Sum LeetCode Solution in C++

class Solution {
 public:
  bool checkSubarraySum(vector<int>& nums, int k) {
    int prefix = 0;
    unordered_map<int, int> prefixToIndex{{0, -1}};

    for (int i = 0; i < nums.size(); ++i) {
      prefix += nums[i];
      if (k != 0)
        prefix %= k;
      if (const auto it = prefixToIndex.find(prefix);
          it != prefixToIndex.cend()) {
        if (i - it->second > 1)
          return true;
      } else {
        // Set a new key if it's absent because the previous index is better.
        prefixToIndex[prefix] = i;
      }
    }

    return false;
  }
};
/* code provided by PROGIEZ */

523. Continuous Subarray Sum LeetCode Solution in Java

class Solution {
  public boolean checkSubarraySum(int[] nums, int k) {
    int prefix = 0;
    Map<Integer, Integer> prefixToIndex = new HashMap<>();
    prefixToIndex.put(0, -1);

    for (int i = 0; i < nums.length; ++i) {
      prefix += nums[i];
      if (k != 0)
        prefix %= k;
      if (prefixToIndex.containsKey(prefix)) {
        if (i - prefixToIndex.get(prefix) > 1)
          return true;
      } else {
        // Set a new key if it's absent because the previous index is better.
        prefixToIndex.put(prefix, i);
      }
    }

    return false;
  }
}
// code provided by PROGIEZ

523. Continuous Subarray Sum LeetCode Solution in Python

class Solution:
  def checkSubarraySum(self, nums: list[int], k: int) -> bool:
    prefix = 0
    prefixToIndex = {0: -1}

    for i, num in enumerate(nums):
      prefix += num
      if k != 0:
        prefix %= k
      if prefix in prefixToIndex:
        if i - prefixToIndex[prefix] > 1:
          return True
      else:
        # Set a new key if it's absent because the previous index is better.
        prefixToIndex[prefix] = i

    return False
 # code by PROGIEZ