{"id":2563,"date":"2018-05-08T20:50:38","date_gmt":"2018-05-08T12:50:38","guid":{"rendered":"https:\/\/boweihe.me\/?p=2563"},"modified":"2018-05-08T20:50:38","modified_gmt":"2018-05-08T12:50:38","slug":"leetcode-523-continuous-subarray-sum","status":"publish","type":"post","link":"https:\/\/dayandcarrot.space\/?p=2563","title":{"rendered":"LeetCode 523. Continuous Subarray Sum"},"content":{"rendered":"<p>https:\/\/leetcode.com\/problems\/continuous-subarray-sum\/description\/<br \/>\n\u8fd9\u9053\u9898\u8ddfhttps:\/\/leetcode.com\/problems\/subarray-sum-equals-k\/description\/ \u5176\u5b9e\u662f\u5f88\u50cf\u7684\uff0c\u4f46\u672c\u9898\u7684\u7279\u70b9\u5c31\u662fcorner case\u975e\u5e38\u591a&#8230;<\/p>\n<pre class=\"lang:c++ decode:true \">class Solution {\npublic:\n    bool checkSubarraySum(vector&lt;int&gt;&amp; nums, int k) {\n        if (k &lt; 0)\n            k = -1 * k;\n        else if (k == 0)\n        {\n            \/\/ check if there's continuous zeroes\n            bool has_zero = false;\n            for (int num : nums)\n            {\n                if (num == 0)\n                {\n                    if (has_zero == true)\n                        return true;\n                    has_zero = true;\n                }\n                else\n                    has_zero = false;\n            }\n            return false;\n        }\n        if (k == 1 &amp;&amp; nums.size() &gt; 1)  \/\/ tricky but...\n            return true;\n        int sum = 0;\n        unordered_set&lt;int&gt; sum_records;\n        vector&lt;int&gt; targets = {k};\n        int last_num = INT32_MAX;\n        sum_records.insert(0);\n        for (int num : nums)\n        {\n            sum += num;\n            sum_records.insert(sum);\n            if (last_num == 0 &amp;&amp; num == 0)\n                return true;    \/\/ n = 0\n            while (targets.back() + k &lt;= sum)\n                targets.push_back(targets.back() + k);  \/\/ prvents calculating dup multiplies\n            for (int target : targets)\n            {\n                if (num != target &amp;&amp; sum_records.count(sum - target) &gt; 0)\n                    return true;\n            }\n            last_num = num;\n        }\n        return false;\n    }\n};<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>https:\/\/leetcode.com\/problems\/continuous-subarray-sum\/description\/ \u8fd9\u9053\u9898\u8ddfhttps:\/\/leetcode.com\/problems\/subarray-sum-equals-k\/description\/ \u5176\u5b9e\u662f\u5f88\u50cf\u7684\uff0c\u4f46\u672c\u9898\u7684\u7279\u70b9\u5c31\u662fcorner case\u975e\u5e38\u591a&#8230; class Solution { public: bool checkSubarraySum(vector&lt;int&gt;&amp; nums, int k) { if (k &lt; 0) k = -1 * k; else if (k == 0) { \/\/ check if there&#8217;s continuous zeroes bool has_zero = false; for (int num : nums) { if (num == 0) { if (has_zero == true) return [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[8],"tags":[66],"class_list":["post-2563","post","type-post","status-publish","format-standard","hentry","category-technical","tag-leetcode-oj"],"_links":{"self":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/2563","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2563"}],"version-history":[{"count":0,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/2563\/revisions"}],"wp:attachment":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2563"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2563"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2563"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}