My o(n) cpp solution

  • 0
    class Solution {
        bool checkSubarraySum(vector<int>& nums, int k) {
            for (int i=0;i<nums.size()-1;i++){
                if (nums[i]==0&&nums[i+1]==0) return true;
            if (k==0)return false;
            map<int, int> m;
            int sum = 0;
            for (int i=0; i<nums.size();i++) {
                if (m.count(sum)) {
                    if (!( m[0]==-1 && i==0))
                    return true;
            return false;
    1. when there are two subsequent 0, whatever k is, we should return true, because 0*k=0;
    2. when k==0 and there are no two subsequent 0, return false;
    3. iterate through the array, sum+=nums[i], calculate the mod = sum%k, if the same mod has appeared before when i=j, then sum(nums(j...i])==n*k
    4. we put m[0]==-1 at the beginning, think nums = {1,1} and k = 2, sum(nums[0...1])%2=0, so this makes it apply the previous statement;
    5. we need to do the check "if (!( m[0]==-1 && i==0))", in case situations like nums={1} and k=1

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.