523. Continuous Subarray Sum

https://leetcode.com/problems/continuous-subarray-sum/

1. Use brute force:

//Time Limit Exceeded
class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        if(nums.size()==0) return false;
        int len = nums.size();
        if(k==0){
            bool zero = false;
            for(int i=0; i<len; i++){
                if(nums[i] == 0) zero = true; 
            }
            if(!zero) return false;
        }
        for(int i=0; i<len; i++){
            for(int j=0; j<len; j++){
                //cout << i << j << endl;
                if(checkSum(nums, k, i, j)) return true;
            }
        }
        return false;
    }
private: 
    bool checkSum(vector<int>& nums, int k, int head, int tail){  
        if(head>=tail) return false; 
        //cout << head << tail << endl;
        int sum = 0;
        for(int i=head; i<=tail; i++){
            sum += nums[i];
        }
        //cout << "sum: " << sum << endl;
        if(k == 0 && sum == 0)
            return true;
        if(k!=0 && sum % k == 0) 
            return true;
        return false;
    }
};

2. Use hashmap:

//need to review later
//24 ms    9.3 MB
class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        if(nums.size()==0) return false;
        int len = nums.size();
        int sum = 0; int prev = 0;
        unordered_set<int> modk;
        for(int i=0; i<len; i++){
            sum += nums[i];
            int mod;
            if(k==0)
                mod = sum;
            else
                mod = sum % k;
            //cout << sum << endl;
            //cout << mod << endl;
            //cout << prev << endl;
            if (modk.count(mod)) return true;
            modk.insert(prev);
            prev = mod;
            /*
            cout << "-" << endl;
            for (const int& x: modk) 
                cout << " " << x;
            cout << endl;
            */
        }
        return false;
    }
};