Array - 15. 3Sum

15. 3Sum

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

思路：

找出数组中三数和的所有组合，解决思路是首先做一个排序，然后对于每一位元素，去找出剩下数组中找出两个数和当前元素三个数和为0就可以，主要要留意重复元素就不用了计算在内。

代码：

go：

func threeSum(nums []int) [][]int {

    var res = make([][]int, 0)
    sort.Ints(nums)
    for i := 0; i < len(nums) - 2; i++ {
        if i > 0 && nums[i] == nums[i-1] {
            continue;
        }
        
        low := i + 1
        high := len(nums) - 1
        sum := 0 - nums[i]
        for low < high {
            if nums[low] + nums[high] == sum {
                res = append(res, []int{nums[i], nums[low], nums[high]})
                // 去重
                for low < high && nums[low] == nums[low+1] {
                    low++
                }
                for low < high && nums[high] == nums[high-1] {
                    high--
                }
                // 下一种
                low++
                high--
            } else if  nums[low] + nums[high] < sum {
                low++
            } else {
                high--
            }
        }
    } 
    
    return res
}