# 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)。 思路如圖所示：  > 在這里之所以要排序解決是因為， 我們算法的瓶頸在這里不在于排序，而在于 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 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。