4Sum Leetcode


#1

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

The solution set must not contain duplicate quadruplets.

Example:

Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

#2

The 4sum leetcode question is very similar to 3 sum leetcode. Sort the input, use first 2 numbers and 2 indexes one at the start and one at end. Also have to check for duplicates at every place.

Below is accepted Golang solution.

func fourSum(nums []int, target int) [][]int {
    result := make([][]int, 0)
    if len(nums) == 0{
        return result
    }
    
    sort.Ints(nums)
    
    for i:=0;i<len(nums);i++{
        if i>0 && nums[i] == nums[i-1]{
            continue
        }
        for j:=i+1; j<len(nums); j++{
            if j> i+1 && nums[j] == nums[j-1] {
                continue
            }
            k, l := j+1, len(nums)-1
            for k < l{
                sum := nums[i]+nums[j]+nums[k]+nums[l]
                if sum == target{
                    result = append(result, []int{nums[i], nums[j], nums[k], nums[l]})
                    k++
                    l--
                    for k < l && nums[k]==nums[k-1]{ k++}
                     for k < l && nums[l]==nums[l+1]{l--}
                } else if sum > target{
                    l--
                } else{
                    k++
                }
            }
        }
    }
    
    return result
}