523. Continuous Subarray Sum
sum Subarray
2023-09-11 14:22:44 时间
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.
Approach #1: Brute force. [C++]
class Solution { public: bool checkSubarraySum(vector<int>& nums, int k) { if (nums.size() < 2) return false; int l = nums.size(); if (k == 0) { for (int i = 0; i < l-1; ++i) if (nums[i] + nums[i+1] == 0) return true; return false; } vector<int> sum(l+1, 0); for (int i = 0; i < l; ++i) sum[i+1] = sum[i] + nums[i]; for (int i = 0; i < l-1; ++i) { for (int j = i+2; j <= l; ++j) { if ((sum[j] - sum[i]) % k == 0) return true; } } return false; } };
sum[i] : the sum of nums from 0 to i;
Approach #2: Set. [C++]
class Solution { public: bool checkSubarraySum(vector<int>& nums, int k) { int n = nums.size(), sum = 0, pre = 0; unordered_set<int> modk; for (int i = 0; i < n; ++i) { sum += nums[i]; int mod = k == 0 ? sum : sum % k; if (modk.count(mod)) return true; modk.insert(pre); pre = mod; } return false; } };
相关文章
- Leetcode: Sum of Two Integers && Summary: Bit Manipulation
- Leetcode: Max Sum of Rectangle No Larger Than K
- Lintcode: Interval Sum II
- Lintcode: Subarray Sum Closest
- Lintcode: Subarray Sum
- 113. Path Sum II
- Sum of Digits / Digital Root
- Mybatis-Plus中正确使用sum聚合函数
- [LeetCode] Minimum Path Sum
- leetcode:Path Sum (路径之和) 【面试算法题】
- Mongodb是用Sum 和Where条件
- [LeetCode] Maximum Sum of 3 Non-Overlapping Subarrays 三个非重叠子数组的最大和
- [LeetCode] 371. Sum of Two Integers 两数之和
- [CareerCup] 18.12 Largest Sum Submatrix 和最大的子矩阵
- [LeetCode] 325. Maximum Size Subarray Sum Equals k 最大子数组之和为k
- [LeetCode] Two Sum II - Input array is sorted 两数之和之二 - 输入数组有序
- [LeetCode] 209. Minimum Size Subarray Sum 最短子数组之和
- [LeetCode] 1. Two Sum 两数之和
- 829. Consecutive Numbers Sum
- 918. Maximum Sum Circular Subarray
- 113. Path Sum II
- 209. Minimum Size Subarray Sum
- 64. Minimum Path Sum
- leetcode 560. Subarray Sum Equals K 和为 K 的子数组(中等)