Leetcode15. 三数之和

Leetcode15. 三数之和

题目:
给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三元组。
注意:答案中不可以包含重复的三元组。
示例:

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

题解:
排序+双指针
1.给数组按照升序排序;
2.排序后固定一个数 nums[i]nums[i]nums[i],

  • 2.1.如果nums[i]nums[i]nums[i]大于 0,则三数之和必然无法等于 000,结束循环;
  • 2.2.如果 nums[i]nums[i]nums[i]== nums[i1]nums[i-1]nums[i−1],则说明该数字重复,会导致结果重复,所以跳过本次循环;
  • 2.3.使用左右指针指向 nums[i]nums[i]nums[i]后面的两端,数字分别为 nums[j]nums[j]nums[j]和 nums[k]nums[k]nums[k],计算三个数的和 sumsumsum 判断是否满足为 000,满足则添加进结果集;
      2.3.1.当 sum==0sum == 0sum==0 时,nums[j]==nums[j+1]nums[j] == nums[j+1]nums[j]==nums[j+1]则会导致结果重复,应该跳过,j=j+1
      2.3.2当 sum==0sum == 0sum==0 时,nums[k]==nums[k1]nums[k] == nums[k−1]nums[k]==nums[k−1] 则会导致结果重复,应该跳过,k = k-1
  • 2.4.如果sum>0sum>0sum>0,则将后一位往前移动,即:k=k1k = k-1k=k−1
  • 2.5.如果sum<0sum<0sum<0,则将前一位往后移动,即:j=j+1j = j+1j=j+1

scala代码:

/**
    *
    * @param nums
    * @return
    */
  def threeSum(nums: Array[Int]): List[List[Int]] = {
    if (nums.length < 3) {
      null
    } else {
      val list = new ListBuffer[ListBuffer[Int]]()
      val nums1 = nums.sorted
      var flag = true
      for (i <- 0 until nums1.length; if (flag)) {
        if (nums1(i) > 0) {
          flag = false
        }
        breakable {
          //如果当前的值和上一个值相同,跳出本次循环,去重
          if (i > 0 && nums1(i) == nums1(i - 1)) {
            break()
          }
          //双指针j,k
          var j = i + 1
          var k = nums1.length - 1
          val target = -nums1(i)
          while (j < k) {
            if (nums1(j) + nums1(k) == target) {
              val curr = new ListBuffer[Int]()
              curr.append(nums1(i))
              curr.append(nums1(j))
              curr.append(nums1(k))
              list.append(curr)
              k = k - 1
              //当左右两个值相等,去重
              while (j < nums1.length && nums1(j) == nums1(j - 1)) j = j + 1
              while (k > j && nums1(k) == nums1(k + 1)) k = k - 1

            } else if (nums1(j) + nums1(k) > target) {
              k = k - 1
            } else {
              j = j + 1
            }
          }
        }
      }
      val result: List[List[Int]] = list.map(_.toList).toList
      result
    }
  }
上一篇:贪心-Bag of Tokens


下一篇:python基础⑧-迭代器和生成器