523. Continuous Subarray Sum
Explanation:
-
Algorithmic Idea:
- We can iterate through the array and keep track of the running sum.
- At each step, we calculate the running sum modulo k.
- If we encounter the same modulo value again, it means the sum of elements between those two indexes is a multiple of k.
- We also need to consider cases where the running sum itself is a multiple of k.
- To handle the case where the subarray size is at least 2, we store the running sum modulo k in a HashMap with initial key 0 and value -1.
- If the difference between the current index and the index stored in the HashMap corresponding to the same modulo value is greater than 1, we have found a good subarray.
-
Time Complexity: O(n) where n is the number of elements in the input array.
-
Space Complexity: O(min(n, k)) where n is the number of elements in the input array.
:
class Solution {
public boolean checkSubarraySum(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
map.put(0, -1);
int 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.get(sum) > 1) {
return true;
}
} else {
map.put(sum, i);
}
}
return false;
}
}Code Editor (Testing phase)
Improve Your Solution
Use the editor below to refine the provided solution. Select a programming language and try the following:
- Add import statement if required.
- Optimize the code for better time or space complexity.
- Add test cases to validate edge cases and common scenarios.
- Handle error conditions or invalid inputs gracefully.
- Experiment with alternative approaches to deepen your understanding.
Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.