Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/523.html
523. 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.
Constraints:
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.
Algorithm
bruce force
note if k is 0 then mod will not work
Code
-
public class Continuous_Subarray_Sum { class Solution { public boolean checkSubarraySum(int[] nums, int k) { // input null check for (int i = 0; i < nums.length; ++i) { int sum = nums[i]; for (int j = i + 1; j < nums.length; ++j) { sum += nums[j]; if (sum == k) return true; if (k != 0 && sum % k == 0) return true; } } return false; } } } ############ class Solution { public boolean checkSubarraySum(int[] nums, int k) { Map<Integer, Integer> mp = new HashMap<>(); mp.put(0, -1); int s = 0; for (int i = 0; i < nums.length; ++i) { s += nums[i]; int r = s % k; if (mp.containsKey(r) && i - mp.get(r) >= 2) { return true; } if (!mp.containsKey(r)) { mp.put(r, i); } } return false; } }
-
// OJ: https://leetcode.com/problems/continuous-subarray-sum // Time: O(N^2) // Space: O(1) class Solution { public: bool checkSubarraySum(vector<int>& nums, int k) { for (int i = 0; i < nums.size(); ++i) { int sum = nums[i]; for (int j = i + 1; j < nums.size(); ++j) { sum += nums[j]; if ((!k && !sum) || (k && sum % k == 0)) return true; } } return false; } };
-
class Solution: def checkSubarraySum(self, nums: List[int], k: int) -> bool: s = 0 mp = {0: -1} for i, v in enumerate(nums): s += v r = s % k if r in mp and i - mp[r] >= 2: return True if r not in mp: mp[r] = i return False ############ class Solution(object): def checkSubarraySum(self, nums, k): """ :type nums: List[int] :type k: int :rtype: bool """ if k == 0: return "0,0" in ",".join([str(n) for n in nums]) if len(nums) < 2: return False if len(nums) == 2: return sum(nums) % k == 0 ppSum = 0 subSum = nums[0] + nums[1] d = set([0]) for i in range(2, len(nums)): ppSum = (ppSum + nums[i - 2]) % k d |= {ppSum} subSum = (subSum + nums[i]) % k if subSum % k in d: return True return False
-
func checkSubarraySum(nums []int, k int) bool { mp := map[int]int{0: -1} s := 0 for i, v := range nums { s += v r := s % k if j, ok := mp[r]; ok && i-j >= 2 { return true } if _, ok := mp[r]; !ok { mp[r] = i } } return false }
-
class Solution { public boolean checkSubarraySum(int[] nums, int k) { int length = nums.length; if (length < 2) return false; if (k == 0) { for (int i = 1; i < length; i++) { if (nums[i - 1] == 0 && nums[i] == 0) return true; } return false; } Map<Integer, Integer> map = new HashMap<Integer, Integer>(); map.put(0, -1); int remainder = 0; for (int i = 0; i < length; i++) { remainder = (remainder + nums[i]) % k; if (map.containsKey(remainder)) { int prevIndex = map.get(remainder); if (i - prevIndex > 1) return true; } else map.put(remainder, i); } return false; } } ############ class Solution { public boolean checkSubarraySum(int[] nums, int k) { Map<Integer, Integer> mp = new HashMap<>(); mp.put(0, -1); int s = 0; for (int i = 0; i < nums.length; ++i) { s += nums[i]; int r = s % k; if (mp.containsKey(r) && i - mp.get(r) >= 2) { return true; } if (!mp.containsKey(r)) { mp.put(r, i); } } return false; } }
-
// OJ: https://leetcode.com/problems/continuous-subarray-sum // Time: O(N^2) // Space: O(1) class Solution { public: bool checkSubarraySum(vector<int>& nums, int k) { for (int i = 0; i < nums.size(); ++i) { int sum = nums[i]; for (int j = i + 1; j < nums.size(); ++j) { sum += nums[j]; if ((!k && !sum) || (k && sum % k == 0)) return true; } } return false; } };
-
class Solution: def checkSubarraySum(self, nums: List[int], k: int) -> bool: s = 0 mp = {0: -1} for i, v in enumerate(nums): s += v r = s % k if r in mp and i - mp[r] >= 2: return True if r not in mp: mp[r] = i return False ############ class Solution(object): def checkSubarraySum(self, nums, k): """ :type nums: List[int] :type k: int :rtype: bool """ if k == 0: return "0,0" in ",".join([str(n) for n in nums]) if len(nums) < 2: return False if len(nums) == 2: return sum(nums) % k == 0 ppSum = 0 subSum = nums[0] + nums[1] d = set([0]) for i in range(2, len(nums)): ppSum = (ppSum + nums[i - 2]) % k d |= {ppSum} subSum = (subSum + nums[i]) % k if subSum % k in d: return True return False
-
func checkSubarraySum(nums []int, k int) bool { mp := map[int]int{0: -1} s := 0 for i, v := range nums { s += v r := s % k if j, ok := mp[r]; ok && i-j >= 2 { return true } if _, ok := mp[r]; !ok { mp[r] = i } } return false }