{"id":194,"date":"2024-10-19T00:37:04","date_gmt":"2024-10-18T16:37:04","guid":{"rendered":"https:\/\/womeifei.cn\/?p=194"},"modified":"2024-10-19T00:37:04","modified_gmt":"2024-10-18T16:37:04","slug":"%e5%92%8c%e4%b8%bak%e7%9a%84%e5%ad%90%e6%95%b0%e7%bb%84","status":"publish","type":"post","link":"https:\/\/womeifei.cn\/index.php\/2024\/10\/19\/%e5%92%8c%e4%b8%bak%e7%9a%84%e5%ad%90%e6%95%b0%e7%bb%84\/","title":{"rendered":"\u548c\u4e3ak\u7684\u5b50\u6570\u7ec4"},"content":{"rendered":"\n
\"\"<\/div><\/figure>\n\n\n\n

\u65b9\u6cd5\u4e00:\u679a\u4e3e<\/p>\n\n\n\n

\"\"<\/div><\/figure>\n\n\n\n
int cnt=0;\nfor(int i=0;i<numsSize;i++)\n{\nint sum=0;\nfor(int j=i=j>=0;j--)\n{\nsum+=nums[j];\nif(sum==target)cnt++;\n}\n}\nreturn cnt;<\/code><\/pre>\n\n\n\n
\u65f6\u95f4\u590d\u6742\u5ea6O(n*n) \u5bf9\u4e8e\u6bcf\u4e2ai\u6211\u4eec\u9700\u8981\u5faa\u73af\u6240\u6709\u7684j \u8fd9\u8fd8\u53ef\u4ee5\u518d\u8fdb\u4e00\u6b65\u4f18\u5316!<\/p>\n\n\n\n
\u65b9\u6cd5\u4e8c:\u54c8\u5e0c\u8868+\u524d\u7f00\u548c<\/p>\n\n\n\n
C++\u6e90\u4ee3\u7801\u5982\u4e0b \u786e\u5b9e\u5f88\u65b9\u4fbf<\/strong><\/p>\n\n\n\n
class Solution {<\/p>\n\n\n\n
public:<\/p>\n\n\n\n
    int subarraySum(vector<int>& nums, int k) {<\/p>\n\n\n\n
       unordered_map<int ,int> mp;<\/p>\n\n\n\n
       mp[0]=1;<\/p>\n\n\n\n
\u00a0 \u00a0 \u00a0 \u00a0int count=0,pre=0;<\/p>\n\n\n\n
\u00a0 \u00a0 \u00a0 \u00a0for(auto&x:nums)\/\/\u904d\u5386\u6570\u7ec4<\/p>\n\n\n\n
       {<\/p>\n\n\n\n
\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 pre+=x;\/\/\u524d\u7f00\u548c<\/p>\n\n\n\n
\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 if(mp.find(pre-k)!=mp.end())\/\/\u5bfb\u627ekey<\/p>\n\n\n\n
            {<\/p>\n\n\n\n
                count+=mp[pre-k];<\/p>\n\n\n\n
            }<\/p>\n\n\n\n
            mp[pre]++;<\/p>\n\n\n\n
       }<\/p>\n\n\n\n
       return count;<\/p>\n\n\n\n
    }<\/p>\n\n\n\n
};<\/p>\n\n\n\n
<\/p>\n\n\n\n
\u4e5f\u53ef\u7528C\u8bed\u8a00\u6570\u7ec4\u6a21\u62dfHash\u8868!!!<\/strong><\/p>\n\n\n\n
#define HASH(n) hashTable[n+10000000]<\/strong><\/p>\n\n\n\n
\/\/\u5f3a\u884c\u4f7f\u4e0b\u6807\u4e0d\u53ef\u80fd\u4e3a\u8d1f\u6570<\/strong><\/p>\n\n\n\n
int subarraySum(int* nums, int numsSize, int k)<\/p>\n\n\n\n
{<\/p>\n\n\n\n
    int hashTable[20000001] = {0};<\/p>\n\n\n\n
    int pre = 0;<\/p>\n\n\n\n
    int count = 0;<\/p>\n\n\n\n
    HASH(0)++;<\/p>\n\n\n\n
    for (int i = 0; i < numsSize; i++) {<\/p>\n\n\n\n
        pre += nums[i];<\/p>\n\n\n\n
        if (HASH(pre – k))<\/p>\n\n\n\n
            count+=HASH(pre-k);<\/p>\n\n\n\n
        HASH(pre)++;<\/p>\n\n\n\n
    }<\/p>\n\n\n\n
    return count;<\/p>\n\n\n\n
}<\/p>\n","protected":false},"excerpt":{"rendered":"
\u65b9\u6cd5\u4e00:\u679a\u4e3e \u65f6\u95f4\u590d\u6742\u5ea6O(n*n) \u5bf9\u4e8e\u6bcf\u4e2ai\u6211\u4eec\u9700\u8981\u5faa\u73af\u6240\u6709\u7684j \u8fd9\u8fd8\u53ef\u4ee5\u518d\u8fdb\u4e00\u6b65\u4f18\u5316! \u65b9\u6cd5\u4e8c:\u54c8\u5e0c\u8868+ […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[8,9],"tags":[],"class_list":["post-194","post","type-post","status-publish","format-standard","hentry","category-8","category-9"],"_links":{"self":[{"href":"https:\/\/womeifei.cn\/index.php\/wp-json\/wp\/v2\/posts\/194","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/womeifei.cn\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/womeifei.cn\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/womeifei.cn\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/womeifei.cn\/index.php\/wp-json\/wp\/v2\/comments?post=194"}],"version-history":[{"count":1,"href":"https:\/\/womeifei.cn\/index.php\/wp-json\/wp\/v2\/posts\/194\/revisions"}],"predecessor-version":[{"id":197,"href":"https:\/\/womeifei.cn\/index.php\/wp-json\/wp\/v2\/posts\/194\/revisions\/197"}],"wp:attachment":[{"href":"https:\/\/womeifei.cn\/index.php\/wp-json\/wp\/v2\/media?parent=194"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/womeifei.cn\/index.php\/wp-json\/wp\/v2\/categories?post=194"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/womeifei.cn\/index.php\/wp-json\/wp\/v2\/tags?post=194"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}