Last Updated on 2021-06-02 by Clay
題目
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:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Input: nums = []
Output: []題目是給定一個全是由『整數』組成的陣列，而我們的目標就是要找出『任意三個數值加總為 0 的所有答案』，也是題目 3Sum 的意義。
還有，返回的結果不能有重複的答案。
解題思路
在解這題以前，我個人就已經有上過一堂名為高等程式設計的課程，裡面就已經有教過如何去解這種類型的題目的標準流程，所以我基本上就是按照當初的教學一步步操作去解題。
沒有太多的思考，少了點鍛鍊的感覺，覺得有些可惜。不過一方面也很慶幸當初上的課居然現在還有印象。
以下為（當初上課）標準的解題步驟
- 先將陣列由大到小排序
- 使用迴圈讀出第 i 個值，同時設定 left 以及 right 兩端座標
- 如果 i 值等於 i-1 值，可以跳過
- left 從 i+1 開始計算
- right 從陣列長度-1 開始計算
- 計算第 i 個值、第 left 個值、第 right 個值加總是否為 0
- 等於 0：確認這是一組答案（儲存起來，最後需要返回全部答案），left 往右移動、right 往左移動
- 小於 0：代表加總值不夠大，將 left 點往右移動，尋更大的值
- 大於 0：代表加總值太大，將 right 點往左移動，尋找更小的值
- 可以通過判斷 left 和 right 移動過後是否和上一組相同，如果相同，這就會是重複答案、跳過
C++ 程式碼
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { // Preventation if (nums.size() <= 2) return {}; // Sort sort(nums.begin(), nums.end()); // Init vector<vector<int>> results; int target = 0; // Find the match ans for (int i=0; i<nums.size(); ++i) { if (i > 0 && nums[i] == nums[i-1]) continue; int left = i+1; int right = nums.size()-1; while (left < right) { if (left > i+1 && right < nums.size()-1) { if (nums[left] == nums[left-1] && nums[right] == nums[right+1]) { ++left; --right; continue; } } int sum = nums[i] + nums[left] + nums[right]; if (sum == 0) { results.push_back({nums[i], nums[left], nums[right]}); ++left; --right; } else if (sum < 0) { ++left; } else if (sum > 0) { --right; } } } return results; } };
Python 程式碼
class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: # Preventation if len(nums) <= 2: return [] # Sort nums.sort() # Init results = [] target = 0 # Find the match ans for i in range(len(nums)): if i > 0 and nums[i] == nums[i-1]: continue left = i + 1 right = len(nums) - 1 while (left < right): if (left > i+1 and right < len(nums)-1): if nums[left] == nums[left-1] and nums[right] == nums[right+1]: left += 1 right -= 1 continue sum_result = nums[i] + nums[left] + nums[right] if sum_result == 0: results.append([nums[i], nums[left], nums[right]]) left += 1 right -= 1 elif sum_result < 0: left += 1 elif sum_result > 0: right -= 1 return results