[LeetCode解題攻略] 18. 4Sum

題目描述

給定一個包含 n 個整數的陣列 nums，傳回所有唯一的四元組 [nums[a], nums[b], nums[c], nums[d]] 的數組，使得：

• 0 <= a、b、c、d < n
• a、b、c 和 d 不同。
• nums[a] + nums[b] + nums[c] + nums[d] == target

可以按任何順序返回答案。

1. 範例 1：

   Input: nums = [1,0,-1,0,-2,2], target = 0
   Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

2. 範例 2：

   Input: nums = [2,2,2,2,2], target = 8
   Output: [[2,2,2,2]]

解題思路

4Sum 是經典的多指針問題，與 Two Sum 和 3Sum 類似。我們的目標是利用排序和雙指針技術來有效地找到所有符合條件的四元組。

主要思路如下：

1. 排序陣列：對陣列進行升序排序，便於後續利用雙指針。
2. 固定兩個數字，解簡化為 Two Sum 問題：
3. • 使用雙重迴圈固定前兩個數字。
   • 對於剩餘的數字，利用雙指針來查找目標和。
3. 去重處理：為了避免重複結果，需要在遍歷和指針移動時進行重複值的檢查。

解法 1：排序 + 四重迴圈暴力解法

思路

1. 直接使用四層迴圈來固定四個數字，檢查它們的總和是否等於目標值 target。
2. 在每層迴圈中檢查重複值，避免結果中出現重複的組合。

實現 (Python)

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()  # 對陣列排序
        n = len(nums)
        result = []
        
        for i in range(n - 3):
            # 避免重複的第一個數
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            for j in range(i + 1, n - 2):
                # 避免重複的第二個數
                if j > i + 1 and nums[j] == nums[j - 1]:
                    continue
                for k in range(j + 1, n - 1):
                    # 避免重複的第三個數
                    if k > j + 1 and nums[k] == nums[k - 1]:
                        continue
                    for l in range(k + 1, n):
                        # 避免重複的第四個數
                        if l > k + 1 and nums[l] == nums[l - 1]:
                            continue
                        if nums[i] + nums[j] + nums[k] + nums[l] == target:
                            result.append([nums[i], nums[j], nums[k], nums[l]])
        return result

時間與空間複雜度

• 時間複雜度：O(n⁴)
• • 排序的時間複雜度是 O(n log n)，四重迴圈的時間複雜度是 O(n⁴)。
• 空間複雜度：O(1)
• • 結果列表佔用的額外空間不計入內。

解法 2：排序 + 雙指針法

思路

1. 排序陣列：對 nums 進行排序，保證結果有序。
2. 雙重迴圈固定前兩個數字：
3. • 使用變數 i 和 j 分別固定第一個和第二個數字。
3. 雙指針處理剩餘兩個數字：
4. • 使用雙指針 left 和 right，分別指向剩餘子陣列的開頭和末尾。
   • 如果四數之和等於目標值，加入結果列表。
   • 調整指針以嘗試其他可能組合，同時注意避免重複值。

實現 (Python)

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()  # 對陣列排序
        n = len(nums)
        result = []
        
        for i in range(n - 3):
            # 避免重複的第一個數
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            for j in range(i + 1, n - 2):
                # 避免重複的第二個數
                if j > i + 1 and nums[j] == nums[j - 1]:
                    continue
                
                # 雙指針法處理剩餘的兩個數
                left, right = j + 1, n - 1
                while left < right:
                    total = nums[i] + nums[j] + nums[left] + nums[right]
                    if total == target:
                        result.append([nums[i], nums[j], nums[left], nums[right]])
                        
                        # 避免重複的第三個數和第四個數
                        while left < right and nums[left] == nums[left + 1]:
                            left += 1
                        while left < right and nums[right] == nums[right - 1]:
                            right -= 1
                        
                        # 繼續移動指針
                        left += 1
                        right -= 1
                    elif total < target:
                        left += 1  # 和太小，增加左指針
                    else:
                        right -= 1  # 和太大，減小右指針
        
        return result

時間與空間複雜度

• 時間複雜度：O(n³)
• • 排序的時間複雜度是 O(n log n)，雙重迴圈 + 雙指針的時間複雜度是 O(n³)。
• 空間複雜度：O(1)
• • 除了結果列表外，無額外空間使用。

總結

在實際問題中，雙指針法是更高效的選擇。熟練掌握 Two Sum、3Sum、4Sum 等問題的解法，對於處理多指針類問題非常有幫助！