My o(n) cpp solution


  • 0
    F
    class Solution {
    public:
        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;
            m[0]=-1;
            int sum = 0;
            for (int i=0; i<nums.size();i++) {
                sum+=nums[i];
                sum%=k;
                if (m.count(sum)) {
                    if (!( m[0]==-1 && i==0))
                    return true;
                }
                m[sum]=i;
            }
            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.