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 <= 10^5
• 0 <= nums[i] <= 10^9
• 0 <= sum(nums[i]) <= 2^31 - 1
• 1 <= k <= 2^31 - 1

## Subarray Sum Multiples

### Problem Description

Given an integer array `nums` and an integer `k`, determine if there exists a non-empty subarray whose sum is a multiple of `k`. The subarray must have a length of at least 2. Return `true` if such a subarray exists, and `false` otherwise.

### Brute Force Solution

The most straightforward approach is to consider every possible subarray, calculate its sum, and check if the sum is a multiple of `k`. This involves two nested loops to define the start and end indices of the subarray. This approach has a time complexity of O(n^2).

```java
class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                int sum = 0;
                for (int l = i; l <= j; l++) {
                    sum += nums[l];
                }
                if (sum % k == 0) {
                    return true;
                }
            }
        }
        return false;
    }
}

Optimized Solution (Using Prefix Sum and HashMap)

We can optimize this using the concept of prefix sums and a HashMap. The idea is to calculate the cumulative sum at each index and store the remainder of the cumulative sum when divided by k in a HashMap. If we encounter the same remainder again, it means that the subarray between those two indices has a sum that is a multiple of k.

import java.util.HashMap;

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

Big(O) Runtime Analysis

The optimized solution iterates through the array once, performing constant-time operations for each element. Therefore, the time complexity is O(n), where n is the length of the input array nums.

Big(O) Space Usage Analysis

The space complexity is determined by the HashMap, which, in the worst case, can store all the remainders of the cumulative sums. In the worst-case scenario, all remainders are distinct, resulting in O(min(n, k)) space complexity, where n is the length of the input array and k is the divisor. If k is smaller than n, the HashMap would store at most k entries.

Edge Cases

1. Empty Array: If the array is empty, there are no subarrays, so return false.
2. Array with Single Element: If the array has only one element, it cannot form a subarray of length at least two, so return false.
3. k = 0: The problem statement specifies 1 <= k <= 2^31 - 1, so we don't need to consider the case where k is 0.
4. All Elements are Zero: If all elements are zero, any subarray will have a sum of zero, which is a multiple of k, so return true if the length is at least 2.
5. k = 1: If k is 1, then any subarray sum is a multiple of k, since any integer is divisible by 1. So we just need to check if the array has at least 2 elements.
6. Large Numbers: The cumulative sum can potentially become very large. Using the modulo operator % avoids integer overflow.