O(n^2) but Easy Understand, Using DP


  • 0
    C

    It has been optimized to O(n) space complexity.

    bool checkSubarraySum(vector<int>& nums, int k)
    {
        int size = nums.size();
    
        // handle with (n * k == 0)
        for(int i = 0; i + 1 < size; ++i)
            if(nums[i] == 0 && nums[i + 1] == 0)        // if there are two continuous zero
                return true;
        
        if(k == 0) return false;            // make sure that (dp[j] % k) is valid
        
        // dp[i][j] represents the sum of sub-array from i to j in array
    
        // vector<vector<int>> dp(size, vector<int>(size, 0));
        vector<int> dp(size, 0);
        for(int i = size - 1; i >= 0; --i)
        {
            // dp[i][i] = nums[i];
            dp[i] = nums[i];
            for(int j = i + 1; j < size; ++j)
            {
                // dp[i][j] = d[i + 1][j] + nums[i];
                dp[j] = dp[j] + nums[i];
                if(dp[j] % k == 0)
                    return true;
            }
        }
        
        return false;
    }
    

Log in to reply
 

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