15. 三數之和
- 2019 年 10 月 4 日
- 筆記
題目描述
給定一個包含 n 個整數的數組 nums，判斷 nums 中是否存在三個元素 a，b，c ，使得 a + b + c = 0 ？找出所有滿足條件且不重複的三元組。
注意：答案中不可以包含重複的三元組。
例如, 給定數組 nums = [-1, 0, 1, 2, -1, -4]， 滿足要求的三元組集合為： [ [-1, 0, 1], [-1, -1, 2] ]
來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/3sum 著作權歸領扣網路所有。商業轉載請聯繫官方授權，非商業轉載請註明出處。
思路
我們採用 分治的思想. 想要找出三個數相加等於0，我們可以數組依次遍歷， 每一項a[i]我們都認為它是最終能夠用組成0中的一個數字，那麼我們的目標就是找到 剩下的元素（除a[i]） 兩個相加等於-a[i].
通過上面的思路，我們的問題轉化為了 給定一個數組，找出其中兩個相加等於給定值， 這個問題是比較簡單的， 我們只需要對數組進行排序，然後雙指針解決即可。加上我們需要外層遍歷依次數組，因此總的時間複雜度應該是O(N^2)。
思路如圖所示：
在這裡之所以要排序解決是因為， 我們演算法的瓶頸在這裡不在於排序，而在於O(N^2)，如果我們瓶頸是排序，就可以考慮別的方式了 如果找某一個特定元素，一個指針就夠了。如果是找兩個元素滿足一定關係（比如求和等於特定值），需要雙指針， 當然前提是數組有序。
關鍵點解析
- 排序之後，用雙指針
- 分治
程式碼
/* * @lc app=leetcode id=15 lang=javascript * * [15] 3Sum * * https://leetcode.com/problems/3sum/description/ * * algorithms * Medium (23.51%) * Total Accepted: 531.5K * Total Submissions: 2.2M * Testcase Example: '[-1,0,1,2,-1,-4]' * * Given an array nums of n integers, are there elements a, b, c in nums such * that a + b + c = 0? Find all unique triplets in the array which gives the * sum of zero. * * Note: * * The solution set must not contain duplicate triplets. * * Example: * * * Given array nums = [-1, 0, 1, 2, -1, -4], * * A solution set is: * [ * [-1, 0, 1], * [-1, -1, 2] * ] * * */ /** * @param {number[]} nums * @return {number[][]} */ var threeSum = function(nums) { if (nums.length < 3) return []; const list = []; nums.sort((a, b) => a - b); for (let i = 0; i < nums.length; i++) { // skip duplicated result without set if (i > 0 && nums[i] === nums[i - 1]) continue; let left = i; let right = nums.length - 1; // for each index i // we want to find the triplet [i, left, right] which sum to 0 while (left < right) { // skip i === left or i === right, in that case, the index i will be used twice if (left === i) { left++; } else if (right === i) { right--; } else if (nums[left] + nums[right] + nums[i] === 0) { list.push([nums[left], nums[right], nums[i]]); // skip duplicated result without set while(nums[left] === nums[left + 1]) { left++; } left++; // skip duplicated result without set while(nums[right] === nums[right - 1]) { right--; } right--; continue; } else if (nums[left] + nums[right] + nums[i] > 0) { right--; } else { left++; } } } return list; };
