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 the 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.
(sum - preSum) % k = 0
=>
sum % k = preSum % k
所以set里面要存的是sum % k,
class Solution { public boolean checkSubarraySum(int[] nums, int k) { if (nums == null || nums.length < 2) return false; if (checkZeros(nums)) return true; if (k == 0) return false; int sum = nums[0]; Set<Integer> set = new HashSet<>(); set.add(0); set.add(sum); for (int i = 1; i < nums.length; i++) { sum += nums[i]; sum %= k; if (set.contains(sum)) { return true; } set.add(sum); } return false; } private boolean checkZeros(int[] nums) { for (int i = 1; i < nums.length; i++) { if (nums[i] == 0 && nums[i - 1] == 0) return true; } return false; } }
560. Subarray Sum Equals K
Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.
Example 1:
Input:nums = [1,1,1], k = 2 Output: 2
Note:
- The length of the array is in range [1, 20,000].
- The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].
class Solution { public int subarraySum(int[] nums, int k) { Map<Integer, Integer> map = new HashMap<>(); map.put(0,1); int sum = 0; int rt = 0; for (int i = 0; i < nums.length; i++) { sum += nums[i]; if (map.containsKey(sum - k)) rt += map.get(sum - k); map.put(sum, map.getOrDefault(sum, 0) + 1); } return rt; } }
No comments:
Post a Comment