18. 4Sum

4sum.go

// https://leetcode.com/problems/4sum/
//
// Time: O(n^3)
// Space: O(1)
//
// n = number of elements in array

// .................... //

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

    res := make([][]int, 0)

    for i := 0; i < n; i++ {
        if i > 0 && nums[i] == nums[i-1] {
             continue 
        }
        
        for j := i+1; j < n; j++ {
            if j > i+1 && nums[j] == nums[j-1] {
                 continue 
            }

            l, r := j+1, n-1

            for l < r {
                sum := nums[i] + nums[j] + nums[l] + nums[r]
                if sum == target { 
                    res = append(res, []int{
                        nums[i], nums[j],
                        nums[l], nums[r],
                    })
                    l++
                    r--
                    for l < r && nums[l] == nums[l-1] {
                        l++
                    }
                    for l < r && nums[r] == nums[r+1] {
                        r--
                    }
                } else if sum > target {
                    r--
                } else {
                    l++
                }
            }
        }
    }

    return res
}