<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>

                ThinkChat2.0新版上線,更智能更精彩,支持會話、畫圖、視頻、閱讀、搜索等,送10W Token,即刻開啟你的AI之旅 廣告
                # 0015. 三數之和 ## 題目地址(15. 三數之和) <https://leetcode-cn.com/problems/3sum/> ## 題目描述 ``` <pre class="calibre18">``` 給你一個包含 n 個整數的數組 nums,判斷 nums 中是否存在三個元素 a,b,c ,使得 a + b + c = 0 ?請你找出所有滿足條件且不重復的三元組。 注意:答案中不可以包含重復的三元組。 示例: 給定數組 nums = [-1, 0, 1, 2, -1, -4], 滿足要求的三元組集合為: [ [-1, 0, 1], [-1, -1, 2] ] ``` ``` ## 前置知識 - 排序 - 雙指針 - 分治 ## 公司 - 阿里 - 字節 ## 思路 我們采用`分治`的思想. 想要找出三個數相加等于 0,我們可以數組依次遍歷, 每一項 a\[i\]我們都認為它是最終能夠用組成 0 中的一個數字,那么我們的目標就是找到 剩下的元素(除 a\[i\])`兩個`相加等于-a\[i\]. 通過上面的思路,我們的問題轉化為了`給定一個數組,找出其中兩個相加等于給定值`, 這個問題是比較簡單的, 我們只需要對數組進行排序,然后雙指針解決即可。 加上我們需要外層遍歷依次數組,因此總的時間復雜度應該是 O(N^2)。 思路如圖所示: ![](https://img.kancloud.cn/25/ae/25ae9ebef03acfeae75b268c3c5000f8_756x506.jpg) > 在這里之所以要排序解決是因為, 我們算法的瓶頸在這里不在于排序,而在于 O(N^2),如果我們瓶頸是排序,就可以考慮別的方式了 > > 如果找某一個特定元素,一個指針就夠了。如果是找兩個元素滿足一定關系(比如求和等于特定值),需要雙指針, 當然前提是數組有序。 ## 關鍵點解析 - 排序之后,用雙指針 - 分治 ## 代碼 ``` <pre class="calibre18">``` <span class="hljs-title">/** * @param {number[]} nums * @return {number[][]} */</span> <span class="hljs-keyword">var</span> threeSum = <span class="hljs-function"><span class="hljs-keyword">function</span> (<span class="hljs-params">nums</span>) </span>{ <span class="hljs-keyword">if</span> (nums.length < <span class="hljs-params">3</span>) <span class="hljs-keyword">return</span> []; <span class="hljs-keyword">const</span> list = []; nums.sort((a, b) => a - b); <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-title">//nums is sorted,so it's impossible to have a sum = 0</span> <span class="hljs-keyword">if</span> (nums[i] > <span class="hljs-params">0</span>) <span class="hljs-keyword">break</span>; <span class="hljs-title">// skip duplicated result without set</span> <span class="hljs-keyword">if</span> (i > <span class="hljs-params">0</span> && nums[i] === nums[i - <span class="hljs-params">1</span>]) <span class="hljs-keyword">continue</span>; <span class="hljs-keyword">let</span> left = i + <span class="hljs-params">1</span>; <span class="hljs-keyword">let</span> right = nums.length - <span class="hljs-params">1</span>; <span class="hljs-title">// for each index i</span> <span class="hljs-title">// we want to find the triplet [i, left, right] which sum to 0</span> <span class="hljs-keyword">while</span> (left < right) { <span class="hljs-title">// since left < right, and left > i, no need to compare i === left and i === right.</span> <span class="hljs-keyword">if</span> (nums[left] + nums[right] + nums[i] === <span class="hljs-params">0</span>) { list.push([nums[left], nums[right], nums[i]]); <span class="hljs-title">// skip duplicated result without set</span> <span class="hljs-keyword">while</span> (nums[left] === nums[left + <span class="hljs-params">1</span>]) { left++; } left++; <span class="hljs-title">// skip duplicated result without set</span> <span class="hljs-keyword">while</span> (nums[right] === nums[right - <span class="hljs-params">1</span>]) { right--; } right--; <span class="hljs-keyword">continue</span>; } <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (nums[left] + nums[right] + nums[i] > <span class="hljs-params">0</span>) { right--; } <span class="hljs-keyword">else</span> { left++; } } } <span class="hljs-keyword">return</span> list; }; ``` ``` **復雜度分析** - 時間復雜度:O(N2)O(N^2)O(N2) - 空間復雜度:取決于排序算法的空間消耗 大家對此有何看法,歡迎給我留言,我有時間都會一一查看回答。更多算法套路可以訪問我的 LeetCode 題解倉庫:<https://github.com/azl397985856/leetcode> 。 目前已經 37K star 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)
                  <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>

                              哎呀哎呀视频在线观看