57.三数之和

Posted by

题目描述

描述

给定一个包含 n 个整数的数组nums,判断nums中是否存在三个元素 a,b,c
,使得a + b + c = 0 ?找出所有满足条件且不重复的三元组。

给出一个有n个整数的数组S,在S中找到三个整数a, b, c,找到所有使得a + b

  • c = 0 的三元组

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

注意事项

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4],满足要求的三元组集合为:[ [-1, 0, 1], [-1, -1, 2]]

在三元组(a, b, c),要求a <= b <= c。
结果不能包含重复的三元组。

解答

注意

这题我们才用排序+双指针的思路来做,遍历排序后的数组,定义指针l和r,分别从当前遍历元素的下一个元素和数组的最后一个元素往中间靠拢,计算结果跟目标对比。

  1. 结果可能有多个解
  2. left和right分别指向的两个不同位置的元素值相同是允许的,两根指针允许同时出现相同的值
  3. i,left和right分别在遇到同一个值两次或两次以上要跳过,即去重,注意体会去重和2的区别,同一指针不允许连续出现一样的值

相关文章

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注