第四週一開始的題目是 560. Subarray Sum Equals K,難易度 Medium,不過這題沒有限制時間,可以直接用暴力解來對付。
官方解法竟然有更暴力的 O(N^3) xD 下面這個就是時間 O(N^2) 空間 O(1) 的解法囉
int subarraySum(vector<int>& nums, int k) {
int ans = 0;
for(int i=0;i <nums.size(); i++){
int cnt = 0;
for(int j=i; j<nums.size(); j++) {
cnt += nums[j];
if(cnt == k)
ans++;
}
}
return ans;
}