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.
Notice that the solution set must not contain duplicate triplets.
Example 1:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]Example 2:
Input: nums = []
Output: []Example 3:
Input: nums = [0]
Output: []解題想法：
這題本來想寫自己的想法下去，但發現這位大大真的寫得太好了，根本無懈可擊，讓我直接引用她的寫法吧，再次感謝 Fion carry，但她是用 C#，會 C# 的也可以學一下大大的寫法，她的文章有圖文並茂喔，值得大家去看。
[Day 7] 演算法刷題 LeetCode 15. 3Sum (Medium)
- 將 array 從小到大升冪排序
- 將須要找出的3個數的 index 分別表示為
first,second,third - 用 for 迴圈計算，並將
first做為 nums 的起始點 - second 則為
first + 1為起始點 - third 則為
nums.Length - 1為起始點 - 並判斷
nums[first] + nums[second] + nums[third] 是否為 0
- 若等於 0，則為解答之一，Add 到 List
- 若小於 0，則代表負數太大，需要將 second 移至下一個較小的負數
(second++) - 若大於 0，則代表正數太大，需要將 third 移至上一個較小的正數
(third--)
7. 另外判斷 first 是否已經重複，若重複則跳過此次迴圈，因為答案也會是一樣的
- 如 {-1, -1, 0, 1, 2}
8. 另外判斷 second 是否已經重複，若重複則 second++，並跳過此次迴圈，因為答案也會是一樣的
- 如 {-4, 2, 2, 2, 3}
7. 與 8. 是讓效能再更好的其中之一條件，不用重複查找已經查找過的數字。 若沒有寫也是會過的哦！
簡單好懂版：
- Runtime: 1648 ms, faster than 13.79%
- Memory Usage: 17.8 MB, less than 7.12%
概念相同，程式縮減版：
- Runtime: 780 ms, faster than 51.52%
- Memory Usage: 16 MB, less than 63.27%
參考文獻：
