leetCode 15 和 16 三数之和

双指针写法

先预排序，再遍历

code 15

func threeSum(nums []int) [][]int {
    target := 0
    res := [][]int{}

    L := len(nums)

    if L < 3 {
        return res
    }

    sort.Ints(nums)

    for index := 0; index < L - 2; index ++ {
        if nums[index] > 0 {
            break
        }
        start := index + 1
    // 去重
        if index > 0 && nums[index] == nums[index - 1] {
            continue
        }

        end := L - 1
        for start < end {
            if nums[index] + nums[start] + nums[end] < target {
                start += 1
        // 去重
                for nums[start] == nums[start - 1] && start < end {
                start += 1
                }
            } else if nums[index] + nums[start] + nums[end] > target {
                end -= 1
        // 去重
                for nums[end] == nums[end + 1] && start < end {
                    end -= 1
                }
            } else {
                res = append(res, []int{nums[index], nums[start], nums[end]})
                start += 1
                end -= 1
        // 去重
                for nums[start] == nums[start - 1] && nums[end] == nums[end + 1] && start < end {
                    start += 1
                    end -= 1
                }
            }

        }
    }

    return res
}

code 16

func threeSumClosest(nums []int, target int) int {
    L := len(nums)

    if L == 0 {
        return target
    }

    sort.Ints(nums)

    delta := nums[0] + nums[1] + nums[2] - target

    for index := 0; index < L - 2; index ++ {
        start := index + 1
        if index > 0 && nums[index] == nums[index - 1] {
            continue
        }

        end := L - 1
        for start < end {
            newDelta := nums[index] + nums[start] + nums[end] - target
            if newDelta == 0 {
                return target
            } 
            if abs(delta) > abs(newDelta) {
                delta = newDelta
            }
            if newDelta < 0 {
                start += 1
                for nums[start] == nums[start - 1] && start < end {
                start += 1
                }
            } else {
                end -= 1
                for nums[end] == nums[end + 1] && start < end {
                    end -= 1
                }
            }         
        }
    }

    return delta + target
}

func abs(num int) int {
    if num >= 0 {
        return num
    } else {
        return -1 * num
    }
}