[Leetcode] 18. 4Sum

進度：第56題

18. 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]]

Get 洪群崴’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

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

思考脈絡

這題其實跟 2Sum, 3Sum 一樣，就只是需要多一層 for loop pointer 來定錨而已

Python 答案

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        len_of_nums = len(nums)
        nums.sort()

        result = []
        for a in range(len_of_nums - 3):
            if a > 0 and nums[a] == nums[a - 1]:
                # Seen before
                continue
            for b in range(a + 1, len_of_nums - 2):
                if b > a + 1 and nums[b] == nums[b - 1]:
                    # Seen before
                    continue
                c = b + 1
                d = len_of_nums - 1
                while c < d:
                    curr_sum = nums[a] + nums[b] + nums[c] + nums[d]
                    if curr_sum == target:
                        result.append([nums[a], nums[b], nums[c], nums[d]])
                        while d - 1 > c and nums[d - 1] == nums[d]:
                            d -= 1
                        d -= 1
                        
                        while c + 1 < d and nums[c + 1] == nums[c]:
                            c += 1
                        c += 1
                    if curr_sum > target:
                        d -= 1
                    
                    if curr_sum < target:
                        c += 1
        
        return result

Golang 答案

func fourSum(nums []int, target int) [][]int {
    lenOfNums := len(nums)
    sort.Ints(nums)

    result := [][]int{}
    for a := 0; a < lenOfNums - 3; a++ {
        if a > 0 && nums[a - 1] == nums[a] {
            continue
        }
        for b := a + 1; b < lenOfNums - 2; b++ {
            if b > a + 1 && nums[b - 1] == nums[b] {
                continue
            }
            c := b + 1
            d := lenOfNums - 1
            for c < d {
                currSum := nums[a] + nums[b] + nums[c] + nums[d]
                if currSum == target {
                    result = append(result, []int{nums[a], nums[b], nums[c], nums[d]})
                    for d - 1 > c && nums[d - 1] == nums[d] {
                        d--
                    }
                    d--
                    for c + 1 < d && nums[c + 1] == nums[c] {
                        c++
                    }
                    c++
                }
                if currSum > target {
                    d--
                } 
                
                if currSum < target {
                    c++
                }
            }
        }
    }
    return result
}