三數之和的golang實現

給定一個包含 n 個整數的數組 nums，判斷 nums 中是否存在三個元素 a，b，c ，使得 a + b + c = 0 ？找出所有滿足條件且不重覆的三元組。

註意：答案中不可以包含重覆的三元組。

例如, 給定數組 nums = [-1, 0, 1, 2, -1, -4]，

滿足要求的三元組集合為：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

我們來看一下圖：

我們先對數組排序，得到如下圖的結果

我們要計算a+b+c=0，先對數組迴圈得到a，然後b就是a的索引+1的值，c是len(nums)-1的值。

如果a+b+c<0的是時候，說明太小了，那b就往右挪一下

反之，如果a+b+c>0，那麼說明太大了，c就往左挪一下

核心代碼：

func threeSum2(nums []int) [][]int {
    //先對數組排序
    sort.Ints(nums)
    result := [][]int{}
    for i := 0; i < len(nums)-1; i++ {
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }
        j := i + 1
        z := len(nums) - 1
        for z > j {
            b := nums[j]
            c := nums[z]
            if nums[i]+b+c > 0 {
                z--
            } else if nums[i]+b+c < 0 {
                j++
            } else {
                item := []int{nums[i], b, c}
                result = append(result, item)
                for j < z && nums[j] == nums[j+1] {
                    j++
                }
                for j < z && nums[z] == nums[z-1] {
                    z--
                }
                j++
                z--
            }
        }
    }
    return result
}

去重技巧：

• 在迴圈一開始的時候，就判斷當前位的值是否跟上一位一樣，一樣的話就跳過
• 在把符合條件的值存進數組的時候，判斷b的下一位是不是和b一樣，判斷c的下一位是不是和c一樣，一樣的話那就直接跳過