第四週一開始的題目是 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;
    }

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料