Posted on by linyf915

[LeetCode] 18. 4Sum

https://leetcode.com/problems/4sum/

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.
Example 1:

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

Example 2:

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

Github Solution

#Time: O(n^3), Space: O(1)
class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums = sorted(nums)
        result = []
        if len(nums) < 4:
            return 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
                low = j+1
                high = len(nums)-1
                while low < high:
                    four_sum = nums[i] + nums[j] + nums[low] + nums[high]
                    if four_sum == target:
                        result.append([nums[i], nums[j], nums[low], nums[high]])
                        while low < high and nums[low] == nums[low+1]:
                            low += 1
                        while low < high and nums[high] == nums[high-1]:
                            high -= 1
                        low += 1
                        high -= 1
                    elif four_sum < target:
                        low += 1
                    else:
                        high -= 1
        return result

解法：

  1. 排序
  2. 先一次for迴圈
  3. 之後裡面就跟3sum一模一樣。

發表留言