Leetcode - 4Sum

violet posted @ Mar 29, 2020 07:50:29 AM in 算法 with tags Algorithm 2sum Golang , 261 阅读

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

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

Same with 3sum. Add a helper to update each index.

func fourSum(nums []int, target int) [][]int {
    if len(nums) < 4 {
        return [][]int{}
    }
    sort.Ints(nums)
    result := [][]int{}
    for i := 0; i < len(nums); i = findNextUniq(nums,i,true) {
        for j := i+1; j < len(nums); j = findNextUniq(nums, j, true) {
            k := j+1
            l := 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 = findNextUniq(nums, k, true)
                    l = findNextUniq(nums, l, false)
                    continue
                }
                if sum < target {
                    k = findNextUniq(nums, k, true)
                } else {
                    l = findNextUniq(nums, l, false)
                }
            }
        }
    }
    return result
}

func findNextUniq(nums []int, index int, toRight bool) int {
    var i int
    if toRight {
        for i = index+1; i < len(nums); i++ {
            if nums[i] != nums[index] {
                return i
            }
        }
    } else {
        for i = index-1; i >= 0; i-- {
            if nums[i] != nums[index] {
                return i
            }
        }
    }
    return i
}