523. Continuous Subarray Sum
https://leetcode.com/problems/continuous-subarray-sum/
Given a list of non-negative numbers and a target integer k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to a multiple of k, that is, sums up to n*k where n is also an integer.
Example 1:
Input: [23, 2, 4, 6, 7], k=6 Output: True Explanation: Because [2, 4] is a continuous subarray of size 2 and sums up to 6.
Example 2:
Input: [23, 2, 6, 4, 7], k=6 Output: True Explanation: Because [23, 2, 6, 4, 7] is an continuous subarray of size 5 and sums up to 42.
Note:
- The length of the array won't exceed 10,000.
- You may assume the sum of all the numbers is in the range of a signed 32-bit integer.
---
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public boolean checkSubarraySum(int[] nums, int k) { | |
| if (nums.length < 2) { | |
| return false; | |
| } | |
| // Two consecutive zeros | |
| for (int i = 0; i < nums.length - 1; i++) { | |
| if (nums[i] == 0 && nums[i + 1] == 0) { | |
| return true; | |
| } | |
| } | |
| if (k == 0) { | |
| return false; | |
| } | |
| k = Math.abs(k); | |
| Map<Integer, Integer> map = new HashMap<Integer, Integer>(); | |
| map.put(0, -1); | |
| int sum = 0; | |
| for (int i = 0; i < nums.length; i++) { | |
| sum += nums[i]; | |
| // If % is repeated and At least length 2 | |
| if (map.containsKey(sum % k) && i - map.get(sum % k) > 1) { | |
| return true; | |
| } | |
| map.put(sum % k, i); | |
| } | |
| return sum % k == 0; | |
| } | |
| } |
