Continous Subarray Sum



In java, the Map.containsKey ,Map.get and Map.put are not O(1). So I think the time complexity of 3th solution is not O(n).
And HashMap.containsKey will invoke the similar logic with HashMap.get , so you can use Map.get to get value with specific key, if it is null, the value with specici key is not stored in Map, then just put it, otherwise it exists, just to check it which could avoid one useless get logic in some occassion.
Thanks.


I must be missing something. In the first brute force approach, what purpose does having three loops serve?
isn't it sufficient to use two loops?
for (int i = 0; i < nums.length; i++) {
int sum = 0;
for (int j = i; j < nums.length; j++) {
sum += nums[j];
// Check condition
}
}
This would cover all possible contiguous subarray sums in my mind and offers a O(n) time O(1) space bruteforce solution. I must be missing something.

@jj17 It is sufficient to use two loops but brute force approach will be considering the subarray, calculating sum of that subarray and then checking the condition. BTW your solution complexity is O(n^2). Thanks.

A little rephrased and easy to understand.
class Solution { public: bool checkSubarraySum(vector<int>& nums, int k) { int n=nums.size(); int i,j; if(n<2) return false; if(k==0){ for(i=0;i<n;i++) if(nums[i]!=0) return false; return true; } unordered_set<int> myset; int mod,pre=0,sum=0; for(j=0;j<n;j++){ sum+=nums[j]; mod=sum%k; if(myset.find(mod)!=myset.end()) return true; else myset.insert(mod); if(j==0) myset.insert(pre); } return false; } };

bool checkSubarraySum(vector<int>& nums, int k) { for (int i = 0; i < nums.size()  1; i++) { int sum = 0; int counter = 0; for (int j = i; j < nums.size(); j++) { sum += nums[j]; if (++counter < 2) continue; if (sum == k  (k != 0 && sum % k == 0)) return true; } } return false; }
That's O(n^2) solution using O(1) space.