leetcode 15. 三数之和

leetcode 15. 三数之和.

题目描述

15. 三数之和 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]] 解释： nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。 nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。 nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。 注意，输出的顺序和三元组的顺序并不重要。 示例 2：

输入：nums = [0,1,1] 输出：[] 解释：唯一可能的三元组和不为 0 。 示例 3：

输入：nums = [0,0,0] 输出：[[0,0,0]] 解释：唯一可能的三元组和为 0 。

提示：

3 <= nums.length <= 3000 -105 <= nums[i] <= 105

解题思路

法1

方法1:暴力三循环\

1. 使用循环的方式遍历三个数的每一种组成方式,判断和是否为0,如果是则记录数据,否则寻找下一组数据
2. 注意:

• 题目要求不能出现相同和数组所以我们需要对数据是否出现进行判断

判断结果列表中是否有数据与当前为0的数据相同,没有的时候才记录数据

• 时间复杂度(O(n^3))
• 空间复杂度(O(n))

法2

双指针法:\

首先对原数组进行排序，然后遍历整个数组，将当前元素设为 nums[i]。

接下来，使用双指针 j 和 k 分别指向数组中剩余部分的开头和结尾，计算当前三元组的和 sum。

如果 sum < 0，则将 j 右移一位；如果 sum > 0，则将 k 左移一位；否则，将这组解加入到结果集中，并将 j 和 k 分别移动到不同的值上，以避免重复。

如果当前元素和前一个元素相同，则跳过当前元素，避免重复。

• 时间复杂度(O(n^2))
• 空间复杂度(O(1))

执行结果

法1

func samepd(n1 [][]int, n2 []int) bool {
 for i := 0; i < len(n1); i++ {
  for j := 0; j < 3; j++ {
   if n1[i][j] != n2[j] {
    break
   } else if j == 2 {
    return false //相同返回失败
   }
  }
 }
 //没有相同的返回true
 return true
}

func threeSum(nums []int) (r [][]int) {
 sort.Ints(nums)
 for i := 0; i < len(nums); i++ {
  for j := i + 1; j < len(nums); j++ {
   for k := j + 1; k < len(nums); k++ {
    if nums[i]+nums[j]+nums[k] == 0 {
     if samepd(r, []int{nums[i], nums[j], nums[k]}) {
      r = append(r, []int{nums[i], nums[j], nums[k]})
     }
    }
   }
  }
  if i+1 < len(nums) {
   if nums[i] == nums[i+1] {
    i++
   }
  }
 }
 return
}

法2

func threeSum(nums []int) [][]int {
    n := len(nums)
    sort.Ints(nums) // 先将数组排序，便于后续去重
    var res [][]int
    for i := 0; i < n-2; i++ {
        if i > 0 && nums[i] == nums[i-1] {
            // 去重，如果当前元素和前一个元素相同，则跳过
            continue
        }
        j, k := i+1, n-1
        for j < k {
            sum := nums[i] + nums[j] + nums[k]
            if sum < 0 {
                j++
            } else if sum > 0 {
                k--
            } else {
                res = append(res, []int{nums[i], nums[j], nums[k]})
                // 去重，如果找到一组解，则将 j 和 k 分别移动到不同的值上，避免重复
                for j < k && nums[j] == nums[j+1] {
                    j++
                }
                for j < k && nums[k] == nums[k-1] {
                    k--
                }
                j++
                k--
            }
        }
    }
    return res
}

执行结果： 通过 显示详情 查看示例代码 添加备注

执行用时： 44 ms , 在所有 Go 提交中击败了 79.70% 的用户 内存消耗： 7.3 MB , 在所有 Go 提交中击败了 80.57% 的用户 通过测试用例： 312 / 312 炫耀一下:

法3