[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]]

解題思路

主要思路如下：

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 等問題的解法，對於處理多指針類問題非常有幫助！