三数之合

三数之和

难度：中等
问题描述：
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有和为 0 且不重复的三元组。【注意：答案中不可以包含重复的三元组】

示例 ：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

链接：原题链接

解法

解法1：暴力求解

• 思路：现将数组按照升序进行排序，由于是有序数组，所以每次遍历不需要重头遍历
• 代码：

  func threeSum(nums []int) [][]int {
  	var zeroList [][]int
  	// 进行增序排列
  	sort.Ints(nums)
  	length := len(nums)
  	// 初始化 a,b，设置为32位的最小值
  	var a,b  = 0x7FFFFFFF, 0x7FFFFFFF
  	for i := 0; i < length; i++ {
  		if i > 0 && nums[i] == nums[i-1] {
  			continue
  		}
  		for j := i+1; j < length; j++ {
  			if j > i+1 && nums[j] == nums[j-1] {
  				continue
  			}
  			for k := j+1; k < length; k++ {
  				if k > j+1 && nums[k] == nums[k-1] {
  					continue
  				}
  				if nums[i] + nums[j] + nums[k] == 0 {
  					if nums[i] == a && nums[j] == b {
  						break
  					}
  					zero := []int{nums[i],nums[j],nums[k]}
  					zeroList = append(zeroList,zero)
  					a = nums[i]
  					b = nums[j]
  				}
  			}
  		}
  	}
  	return zeroList
  }

  时间复杂度：O(N^3)
  空间复杂度：O(N)
  注：这个代码，放在leetcode 上显示运行超时，本地测试用例是通过的

解法2：双指针

• 思路：先对数组按照升序进行排列，然后使用双指针从两边往中间检索，这样最终只需要O(N^2)的时间内就能完成，遍历过程中要注意重复元素的跳跃
• 解法：

  func threeSumWihtTwoPoint(nums []int)[][] int {
  	// 总来存放所有的 0 值的组合
  	var zeroList [][]int
  	length := len(nums)
  	// 对输入的数组进行排序
  	sort.Ints(nums)
  	
  	// 最多只需要遍历到第 length - 2 即可 
  	for i := 0; i < length - 2; i++ {
  		// 跳过连续重复的字符
  		if i > 0 && nums[i] == nums[i-1] {
  			continue
  		}
  		rightmost := length - 1
  		for j := i + 1; j < length - 1; j++ {
  			// 跳过连续重复的字符
  			if  j > i +1 && nums[j] == nums[j-1] {
  				continue
  			}
  			// 利用单调增的属性，快速确定范围
  			for j < rightmost && nums[i] + nums[j] + nums[rightmost] > 0 {
  				rightmost--
  			}
  			// 双指针相遇，当前遍历结束
  			if j >= rightmost {
  				break
  			}
  			if nums[i] + nums[j] + nums[rightmost] == 0 {
  				zero := []int{nums[i],nums[j],nums[rightmost]}
  				zeroList = append(zeroList, zero)
  			}
  		}
  	}
  	return zeroList
  }

  时间复杂度：O(N^2)
  空间复杂度：O(N)