今天是紀錄LeetCode解題的第十八天

第十八題題目：Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

• 0 <= a, b, c, d < n
• a, b, c, and d are distinct.
• nums[a] + nums[b] + nums[c] + nums[d] == target

You may return the answer in any order.

給定一個整數數組nums，長度為n，傳回所有不重複的四元組[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

可以以任意順序返回結果

解題思路

這題和第十五題是雷同的題目，從3Sum延伸成4Sum，用一樣的概念，原本是固定一個數的索引i，雙指針去找出另外兩個數使得三個數相加等於0，這題則是變成固定兩個數，一樣用雙指針去找出其它兩個數使四個數相加等於target，如果還不了解運作過程的可以看Day15的文章

程式碼

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        result = []
        for i in range(len(nums) - 3):
            if i > 0 and nums[i] == nums[i-1]:
                continue  #避免重複   
            for j in range(i+1,len(nums) - 2):
                if j > i + 1 and nums[j] == nums[j-1]:
                    continue
                l, r = j + 1, len(nums) - 1 
                while l < r:
                    s = nums[i] + nums[j] + nums[l] + nums[r]
                    if s == target:
                        result.append([nums[i], nums[j], nums[l], nums[r]])
                        l += 1
                        r -= 1
                        #跳過重複值
                        while l < r and nums[l] == nums[l-1]:
                            l += 1
                        while l < r and nums[r] == nums[r+1]:
                            r -= 1
                    elif s < target:
                        l += 1
                    else:
                        r -= 1                   
        return result

這題就只是把3Sum的程式碼多了一層for迴圈，其餘概念皆不變