<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國際加速解決方案。 廣告
                # 0494. 目標和 ## 題目地址(494. 目標和) <https://leetcode-cn.com/problems/target-sum/> ## 題目描述 ``` <pre class="calibre18">``` 給定一個非負整數數組,a1, a2, ..., an, 和一個目標數,S。現在你有兩個符號 + 和 -。對于數組中的任意一個整數,你都可以從 + 或 -中選擇一個符號添加在前面。 返回可以使最終數組和為目標數 S 的所有添加符號的方法數。 示例: 輸入:nums: [1, 1, 1, 1, 1], S: 3 輸出:5 解釋: -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 一共有5種方法讓最終目標和為3。 提示: 數組非空,且長度不會超過 20 。 初始的數組的和不會超過 1000 。 保證返回的最終結果能被 32 位整數存下。 ``` ``` ## 前置知識 - 動態規劃 ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ## 思路 題目是給定一個數組,讓你在數字前面添加 `+`或者`-`,使其和等于 target. ![](https://img.kancloud.cn/25/22/2522a8c5272d2a5fdb1b88c55018470f_676x276.jpg) 暴力法的時間復雜度是指數級別的,因此我們不予考慮。我們需要換種思路. 我們將最終的結果分成兩組,一組是我們添加了`+`的,一組是我們添加了`-`的。 ![](https://img.kancloud.cn/1e/7a/1e7a43c785f3fa9c1713b2df83275bf7_812x198.jpg) 如上圖,問題轉化為如何求其中一組,我們不妨求前面標`+`的一組 > 如果求出一組,另一組實際就已知了,即總集和這一組的差集。 通過進一步分析,我們得到了這樣的關系: ![](https://img.kancloud.cn/be/04/be04d0da3a2de9f11ce4a8e92d6cbc44_748x249.jpg) 因此問題轉化為,求解`sumCount(nums, target)`,即 nums 數組中能夠組成 target 的總數一共有多少種,這是一道我們之前做過的題目,使用動態規劃可以解決。 ## 關鍵點解析 - 對元素進行分組,分組的依據是符號, 是`+` 或者 `-` - 通過數學公式推導可以簡化我們的求解過程,這需要一點`數學知識和數學意識` ## 代碼 ``` <pre class="calibre18">``` <span class="hljs-title">/* * @lc app=leetcode id=494 lang=javascript * * [494] Target Sum * */</span> <span class="hljs-title">// 這個是我們熟悉的問題了</span> <span class="hljs-title">// 我們這里需要求解的是nums里面有多少種可以組成target的方式</span> <span class="hljs-keyword">var</span> sumCount = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params">nums, target</span>) </span>{ <span class="hljs-title">// 這里通過觀察,我們沒必要使用二維數組去存儲這些計算結果</span> <span class="hljs-title">// 使用一維數組可以有效節省空間</span> <span class="hljs-keyword">const</span> dp = <span class="hljs-params">Array</span>(target + <span class="hljs-params">1</span>).fill(<span class="hljs-params">0</span>); dp[<span class="hljs-params">0</span>] = <span class="hljs-params">1</span>; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-params">0</span>; i < nums.length; i++) { <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> j = target; j >= nums[i]; j--) { dp[j] += dp[j - nums[i]]; } } <span class="hljs-keyword">return</span> dp[target]; }; <span class="hljs-keyword">const</span> add = nums => nums.reduce((a, b) => (a += b), <span class="hljs-params">0</span>); <span class="hljs-title">/** * @param {number[]} nums * @param {number} S * @return {number} */</span> <span class="hljs-keyword">var</span> findTargetSumWays = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params">nums, S</span>) </span>{ <span class="hljs-keyword">const</span> sum = add(nums); <span class="hljs-keyword">if</span> (sum < S) <span class="hljs-keyword">return</span> <span class="hljs-params">0</span>; <span class="hljs-keyword">if</span> ((S + sum) % <span class="hljs-params">2</span> === <span class="hljs-params">1</span>) <span class="hljs-keyword">return</span> <span class="hljs-params">0</span>; <span class="hljs-keyword">return</span> sumCount(nums, (S + sum) >> <span class="hljs-params">1</span>); }; ``` ``` **復雜度分析** - 時間復雜度:O(N?target)O(N \* target)O(N?target) - 空間復雜度:O(target)O(target)O(target) 大家對此有何看法,歡迎給我留言,我有時間都會一一查看回答。更多算法套路可以訪問我的 LeetCode 題解倉庫:<https://github.com/azl397985856/leetcode> 。 目前已經 37K star 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg) ## 擴展 如果這道題目并沒有限定所有的元素以及 target 都是正數怎么辦?
                  <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>

                              哎呀哎呀视频在线观看