Leetcode 523. Continuous Subarray Sum

source url

题目描述

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.

输入：数组及整数k 输出：该数组的子数组（至少包含两个元素）是否能被k整除

思路

贪心：如题目所示，由于题目要求为子数组，即各元素要求连续。考虑通过计算偏序和的方式，以psum[i]表示到第i个元素的和，某两个元素之间的和可以通过psum[j]-psum[i]来表示。 若存在一个(i,j)使得(psum[j]-psum[i])%k==0 && j-i>=2则存在，否则不存在

复杂度 O(n2)

代码

class Solution { public: bool checkSubarraySum(vector<int>& nums, int k) { if(nums.size()<2) return false; vector<int> psum(nums.size()+1,0); partial_sum( nums.begin(), nums.end(), psum.begin()+1); int cnt = 0; for(int i = 0;i<=nums.size()-2;i++){ cnt = 0; for(int j = i+2;j<=nums.size();j++){ if(k!=0){ if((psum[j]-psum[i])%k==0) return true; }else{ if((psum[j]-psum[i])==0){ return true; } } } } return false; } };