M-18. 4Sum

Loading...LeetCode

# O(n^3), 3SUM外面套了一层循环, 添加了一些限制条件, 自己慢慢品味吧...
class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        res = []
        nums.sort()
        for j in range(len(nums)-3):
            if j > 0 and nums[j] == nums[j-1]:
                    continue
            for i in range(j + 1, len(nums)-2):
                if i > j+1 and nums[i] == nums[i-1]:
                    continue
                l, r = i+1, len(nums)-1
                while l < r:
                    s = nums[i] + nums[l] + nums[r] + nums[j]
                    if s < target:
                        l += 1 
                    elif s > target:
                        r -= 1
                    else:
                        res.append([nums[i], nums[l], nums[r], nums[j]])
                        while l < r and nums[l] == nums[l+1]:
                            l += 1
                        while l < r and nums[r] == nums[r-1]:
                            r -= 1
                        l += 1; r -= 1
        return res