<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                合規國際互聯網加速 OSASE為企業客戶提供高速穩定SD-WAN國際加速解決方案。 廣告
                # 0560. 和為K的子數組 ## 題目地址(560. 和為K的子數組) <https://leetcode-cn.com/problems/subarray-sum-equals-k/> ## 題目描述 ``` <pre class="calibre18">``` 給定一個整數數組和一個整數 k,你需要找到該數組中和為 k 的連續的子數組的個數。 示例 1 : 輸入:nums = [1,1,1], k = 2 輸出: 2 , [1,1] 與 [1,1] 為兩種不同的情況。 說明 : 數組的長度為 [1, 20,000]。 數組中元素的范圍是 [-1000, 1000] ,且整數 k 的范圍是 [-1e7, 1e7]。 ``` ``` ## 前置知識 - 哈希表 - 前綴和 ## 公司 - 阿里 - 騰訊 - 字節 ## 思路 符合直覺的做法是暴力求解所有的子數組,然后分別計算和,如果等于 k,count 就+1.這種做法的時間復雜度為 O(n^2),代碼如下: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">subarraySum</span><span class="hljs-params">(self, nums: List[int], k: int)</span> -> int:</span> cnt, n = <span class="hljs-params">0</span>, len(nums) <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n): sum = <span class="hljs-params">0</span> <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(i, n): sum += nums[j] <span class="hljs-keyword">if</span> (sum == k): cnt += <span class="hljs-params">1</span> <span class="hljs-keyword">return</span> cnt ``` ``` 實際上剛開始看到這題目的時候,我想“是否可以用滑動窗口解決?”。但是很快我就放棄了,因為看了下數組中項的取值范圍有負數,這樣我們擴張或者收縮窗口就比較復雜。第二個想法是前綴和,保存一個數組的前綴和,然后利用差分法得出任意區間段的和,這種想法是可行的,代碼如下: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">subarraySum</span><span class="hljs-params">(self, nums: List[int], k: int)</span> -> int:</span> cnt, n = <span class="hljs-params">0</span>, len(nums) pre = [<span class="hljs-params">0</span>] * (n + <span class="hljs-params">1</span>) <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-params">1</span>, n + <span class="hljs-params">1</span>): pre[i] = pre[i - <span class="hljs-params">1</span>] + nums[i - <span class="hljs-params">1</span>] <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-params">1</span>, n + <span class="hljs-params">1</span>): <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(i, n + <span class="hljs-params">1</span>): <span class="hljs-keyword">if</span> (pre[j] - pre[i - <span class="hljs-params">1</span>] == k): cnt += <span class="hljs-params">1</span> <span class="hljs-keyword">return</span> cnt ``` ``` 這里有一種更加巧妙的方法,可以不使用前綴和數組,而是使用 hashmap 來簡化時間復雜度,這種算法的時間復雜度可以達到 O(n). 具體算法: - 維護一個 hashmap,hashmap 的 key 為累加值 acc,value 為累加值 acc 出現的次數。 - 迭代數組,然后不斷更新 acc 和 hashmap,如果 acc 等于 k,那么很明顯應該+1. 如果 hashmap\[acc - k\] 存在,我們就把它加到結果中去即可。 語言比較難以解釋,我畫了一個圖來演示 nums = \[1,2,3,3,0,3,4,2\], k = 6 的情況。 ![](https://img.kancloud.cn/8a/1e/8a1ef03d6d6c80091d8d3fab54eeee03_785x517.jpg) 如圖,當訪問到 nums\[3\]的時候,hashmap 如圖所示,這個時候 count 為 2. 其中之一是\[1,2,3\],這個好理解。還有一個是\[3,3\]. 這個\[3,3\]正是我們通過 hashmap\[acc - k\]即 hashmap\[9 - 6\]得到的。 ## 關鍵點解析 - 前綴和 - 可以利用 hashmap 記錄和的累加值來避免重復計算 ## 代碼 - 語言支持:JS, Python Javascript Code: ``` <pre class="calibre18">``` <span class="hljs-title">/* * @lc app=leetcode id=560 lang=javascript * * [560] Subarray Sum Equals K */</span> <span class="hljs-title">/** * @param {number[]} nums * @param {number} k * @return {number} */</span> <span class="hljs-keyword">var</span> subarraySum = <span class="hljs-function"><span class="hljs-keyword">function</span> (<span class="hljs-params">nums, k</span>) </span>{ <span class="hljs-keyword">const</span> hashmap = {}; <span class="hljs-keyword">let</span> acc = <span class="hljs-params">0</span>; <span class="hljs-keyword">let</span> count = <span class="hljs-params">0</span>; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-params">0</span>; i < nums.length; i++) { acc += nums[i]; <span class="hljs-keyword">if</span> (acc === k) count++; <span class="hljs-keyword">if</span> (hashmap[acc - k] !== <span class="hljs-keyword">void</span> <span class="hljs-params">0</span>) { count += hashmap[acc - k]; } <span class="hljs-keyword">if</span> (hashmap[acc] === <span class="hljs-keyword">void</span> <span class="hljs-params">0</span>) { hashmap[acc] = <span class="hljs-params">1</span>; } <span class="hljs-keyword">else</span> { hashmap[acc] += <span class="hljs-params">1</span>; } } <span class="hljs-keyword">return</span> count; }; ``` ``` Python Code: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">subarraySum</span><span class="hljs-params">(self, nums: List[int], k: int)</span> -> int:</span> d = {} acc = count = <span class="hljs-params">0</span> <span class="hljs-keyword">for</span> num <span class="hljs-keyword">in</span> nums: acc += num <span class="hljs-keyword">if</span> acc == k: count += <span class="hljs-params">1</span> <span class="hljs-keyword">if</span> acc - k <span class="hljs-keyword">in</span> d: count += d[acc-k] <span class="hljs-keyword">if</span> acc <span class="hljs-keyword">in</span> d: d[acc] += <span class="hljs-params">1</span> <span class="hljs-keyword">else</span>: d[acc] = <span class="hljs-params">1</span> <span class="hljs-keyword">return</span> count ``` ``` ## 擴展 這是一道類似的題目,但是會稍微復雜一點, 題目地址: [437.path-sum-iii](437.path-sum-iii.html)
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看