func twoSum(nums []int, target int) []int {
    contains := make(map[int]int, len(nums))
    for i, num := range nums {
        contains[num] = i
    }

    for j, num := range nums {
        if i, exist := contains[target-num]; i != j && exist {
            return []int{i, j}
        }
    }

    return nil
}

func twoSum(nums []int, target int) []int {
    sort.Ints(nums)

    i, j := 0, len(nums)-1
    for i < j {
        sum := nums[i] + nums[j]
        if sum = target {
            return []int{nums[i], nums[j]}
        } else if sum < target {
            i++
        } else {
            j--
        }
    }

    return nil
}

func threeSum(nums []int) (results [][]int) {
    sort.Ints(nums)

    k := 0
    for k < len(nums) {
        partResults := twoSum(nums[k+1:], -nums[k])
        for _, r := range partResults {
            results = append(results,
                append([]int{nums[k]}, r...),
            )
        }

        for v := nums[k]; k < len(nums) && nums[k] == v; k++ {}
    }
    
    return
}

func twoSum(nums []int, target int) (results [][]int) {
    i, j := 0, len(nums)-1
    for i < j {
        sum := nums[i] + nums[j]
        if sum == target {
            results = append(results, []int{nums[i], nums[j]})

            for v := nums[i]; i < len(nums) && nums[i] == v; i++ {}
            for v := nums[j]; j >= 0 && nums[j] == v; j-- {}
        } else if sum < target {
            for v := nums[i]; i < len(nums) && nums[i] == v; i++ {}
        } else {
            for v := nums[j]; j >= 0 && nums[j] == v; j-- {}
        }
    }
    return 
}

func fourSum(nums []int, target int) (results [][]int) {
    sort.Ints(nums)

    i := 0
    for i < len(nums) - 3 {
        j := len(nums) - 1
        for i + 2 < j {
            partResults := twoSum(nums[i+1:j], target-(nums[i]+nums[j]))
            for _, r := range partResults {
                results = append(results,
                    []int{nums[i], r[0], r[1], nums[j]},
                )
            }
            for v := nums[j]; j > i+2 && nums[j] == v; j-- {}
        } 
         for v := nums[i]; i < len(nums)-3 && nums[i] == v; i++ {}
    }

    return
}

func twoSum(nums []int, target int) (results [][]int) {
    i, j := 0, len(nums)-1
    for i < j {
        sum := nums[i] + nums[j]
        if sum == target {
            results = append(results, []int{nums[i], nums[j]})

            for v := nums[i]; i < len(nums) && nums[i] == v; i++ {}
            for v := nums[j]; j >= 0 && nums[j] == v; j-- {}
        } else if sum < target {
            for v := nums[i]; i < len(nums) && nums[i] == v; i++ {}
        } else {
            for v := nums[j]; j >= 0 && nums[j] == v; j-- {}
        }
    }
    return
}

func fourSum(nums []int, target int) (results [][]int) {
    sort.Ints(nums)

    i := 0
    for i < len(nums) - 3 {
        partResults := threeSum(nums[i+1:], target-nums[i])
        for _, r := range partResults {
            results = append(results,
                append([]int{nums[i]}, r...),
            )
        }
        
        for v := nums[i]; i < len(nums)-3 && nums[i] == v; i++ {}
    }

    return
}

func threeSum(nums []int, target int) (results [][]int) {
    sort.Ints(nums)

    k := 0
    for k < len(nums) {
        partResults := twoSum(nums[k+1:], target-nums[k])
        for _, r := range partResults {
            results = append(results,
                append([]int{nums[k]}, r...),
            )
        }

        for v := nums[k]; k < len(nums) && nums[k] == v; k++ {}
    }
    
    return
}

func twoSum(nums []int, target int) (results [][]int) {
    i, j := 0, len(nums)-1
    for i < j {
        sum := nums[i] + nums[j]
        if sum == target {
            results = append(results, []int{nums[i], nums[j]})

            for v := nums[i]; i < len(nums) && nums[i] == v; i++ {}
            for v := nums[j]; j >= 0 && nums[j] == v; j-- {}
        } else if sum < target {
            for v := nums[i]; i < len(nums) && nums[i] == v; i++ {}
        } else {
            for v := nums[j]; j >= 0 && nums[j] == v; j-- {}
        }
    }
    return 
}

// nums should be already sorted
func nSum(nums []int, target int, n int) (results [][]int) {
    if n == 2 {
        return twoSum(nums, target)
    }

    i := 0
    for i < len(nums)-n+1 {
        partResults := nSum(nums[i+1:], target-nums[i], n-1)
        for _, r := range partResults {
            results = append(results,
              append([]int{nums[i]}, r...),
            )
        }

        for v := nums[i]; i < len(nums)-n+1 && nums[i] == v; i++ {}
    }

    return
}

func twoSum(nums []int, target int) (results [][]int) {
    i, j := 0, len(nums)-1
    for i < j {
        sum := nums[i] + nums[j]
        if sum == target {
            results = append(results, []int{nums[i], nums[j]})

            for v := nums[i]; i < len(nums) && nums[i] == v; i++ {}
            for v := nums[j]; j >= 0 && nums[j] == v; j-- {}
        } else if sum < target {
            for v := nums[i]; i < len(nums) && nums[i] == v; i++ {}
        } else {
            for v := nums[j]; j >= 0 && nums[j] == v; j-- {}
        }
    }
    return 
}

// 使用示例（利用 4Sum）做演示
func fourSum(nums []int, target int) (results [][]int) {
    sort.Ints(nums)

    return nSum(nums, target, 4)
}

func sortColors(nums []int)  {
    i, j := 0, len(nums)-1
    for i <= j {
        if nums[i] == 2 {
            nums[i], nums[j] = nums[j], nums[i]
            j--
        } else {
            i++
        }
    }


    i=0
    for i <= j {
        if nums[i] == 1 {
            nums[i], nums[j] = nums[j], nums[i]
            j--
        } else {
            i++
        }
    }
}

func sortColors(nums []int)  {
    p0, p2 := 0, len(nums)-1

    p := 0
    for p <= p2 {
        if nums[p] == 0 {
            nums[p0], nums[p] = nums[p], nums[p0]
            p0++
        } else if nums[p] == 2 {
            nums[p], nums[p2] = nums[p2], nums[p]
            p2--
        } else {
            p++
        }

        if p < p0 {
            p = p0
        }
    }
}