Skip to content

LeetCode: 15-3Sum 解題紀錄

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


References

Tags:

Leave a Reply