Skip to content

腾讯&leetcode15：三数之和 #31

Open
Open
腾讯&leetcode15：三数之和#31
Labels
LeetCode腾讯

Description

@sisterAn
sisterAn
opened on Apr 29, 2020

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

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

示例：

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

附赠leetcode地址：leetcode

可结合 字节&leetcode1：两数之和 一起查看

Activity

  1. huangruitian commented on Apr 30, 2020

    @huangruitian
    huangruitian
    on Apr 30, 2020
    //这道题经典的是细节，需要考虑蛮多细节的
//解法：
//1.暴力破解，三层枚举，O（n^3）效率太低不考虑
//2.a+b+c = 0，转换思路，a+b = -c，这不就是两数之和嘛？
//3.利用双指针夹逼，但是怎么避免重复呢？
//3.1 排序即可，利用排序好的数组，固定一个指针i，夹逼选举left和right
//3.2 这道题难度在于要考虑的细节太多，多想想即可。
//3.3 扩展一下，如果是4数之和，五数之和，N数之和呢？怎么解决？
const threeSum = (nums) => {
  const len = nums.length
  const result = []
  // 因为是三数之和，小于三个不用考虑了
  if(len < 3){
    return result
  }
  nums.sort((a, b) => a - b)
  // len - 2 同样道理，小于三个不用考虑
  for(let i = 0; i < len - 2; i++){
    // 如果第一个就大于0了，三个加起来肯定大于0
    if(nums[i] > 0){
      break
    }
    // 避免掉重复的情况
    if(i && nums[i] === nums[i - 1]){
       continue
    }
    let left = i + 1
    let right = len - 1
    // 双指针夹逼
    while(left < right){
      const sum = nums[i] + nums[left] + nums[right]
      if(sum === 0){
         result.push([nums[i], nums[left++], nums[right--]])
         // push 加了之后防止还存在重复
         while(nums[left] === nums[left - 1]){
           left++
         }
         while(nums[right] === nums[right + 1]){
           right--
         } 
      }else if(sum > 0){
          right--
      }else{
          left++
      }
    }
  }
  return result
}

  2. thxiami commented on Apr 30, 2020

    @thxiami
    thxiami
    on Apr 30, 2020

    @huangruitian
    1.双指针寻找两数之和的方法挺巧妙的~ 可以用二分法进一步加快一下紧逼速度
    2. K数之和的问题, 目前的思路也是类似将三数之和降为两数之和的办法.
    假设数组有 n 个数, 求满足 K 个数之和为sum的所有组合.
    a. 利用O(nlogn) 的时间排序
    b. 一个循环将问题拆分为 n 个(K-1)数之和, 时间复杂度为 T(K) = O(n * T(K-1)) = O(n^(k-1))

        // 双指针夹逼
    while(left < right){
      const sum = nums[i] + nums[left] + nums[right]
      if(sum === 0){
         result.push([nums[i], nums[left++], nums[right--]])
         // push 加了之后防止还存在重复
         while(nums[left] === nums[left - 1]){
           left++
         }
         while(nums[right] === nums[right + 1]){
           right--
         } 
      }else if(sum > 0){ 
          // 这里可以使用二分法进一步加快寻找符合条件的 right, 即 nums[right]= 0 - nums[i] - nums[left]
          // right--
      }else{ // 同理也可以用二分法加快逼近速度
          // left++
      }
    }
  }

  3. huangruitian commented on Apr 30, 2020

    @huangruitian
    huangruitian
    on Apr 30, 2020
    right

    @huangruitian
    1.双指针寻找两数之和的方法挺巧妙的~ 可以用二分法进一步加快一下紧逼速度
    2. K数之和的问题, 目前的思路也是类似将三数之和降为两数之和的办法.
    假设数组有 n 个数, 求满足 K 个数之和为sum的所有组合.
    a. 利用O(nlogn) 的时间排序
    b. 一个循环将问题拆分为 n 个(K-1)数之和, 时间复杂度为 T(K) = O(n * T(K-1)) = O(n^(k-1))

        // 双指针夹逼
    while(left < right){
      const sum = nums[i] + nums[left] + nums[right]
      if(sum === 0){
         result.push([nums[i], nums[left++], nums[right--]])
         // push 加了之后防止还存在重复
         while(nums[left] === nums[left - 1]){
           left++
         }
         while(nums[right] === nums[right + 1]){
           right--
         } 
      }else if(sum > 0){ 
          // 这里可以使用二分法进一步加快寻找符合条件的 right, 即 nums[right]= 0 - nums[i] - nums[left]
          // right--
      }else{ // 同理也可以用二分法加快逼近速度
          // left++
      }
    }
  }

    不错，对left 和 right的寻找速度用二分法确实是一个优化，很棒！K数之和的复杂度也补充得很棒。

  4. sisterAn commented on Apr 30, 2020

    @sisterAn
    sisterAn
    on Apr 30, 2020
    OwnerAuthor

    解法： 排序 + 双指针

    我们可以继续按照两数之和的思路解题，遍历数组，选定一个数（ nums[i] ）作为三数之和的第一个数，然后题目就换成了在 i+1 到 nums.length-1 中两数之和问题。

    但会出现一个问题：结果中可能会出现重复的三元组

    const threeSum = function(nums) {
    let map = new Map()
    let result = []
    for(let i = 0; i < nums.length - 2; i++) {
        // 第一个数
        let first = nums[i]
        for(let j = i+1; j < nums.length; j++) {
            // 第三个数
            let second = 0 - nums[j] - first
            if(map.has(second)) {
                result.push([first, second, nums[j]])
            }
            map.set(nums[j], j)
        }
        map.clear()
    }
    return result
};

// 测试
var nums = [-1, 0, 1, 2, -1, -4]
threeSum(nums)
// [[-1,0,1],[-1,2,-1],[0,1,-1]]
// 存在重复元组

    你可以尝试着去除重复元组，但花费的时间、空间复杂度就高了

    感谢 @thxiami 的补充，我们可以使用排序去重：

    const threeSum = function (nums) {
  let set = new Set() // 使用 Set() 即可满足需求, 相对节省内存
  let result = []
  nums.sort((a, b) => (a - b))

  for(let i =0; i < nums.length - 2; i++) {
    while (nums[i] === nums[i - 1]) {i++} // 去重
    // 第一个数
    let first = nums[i]
    let j = i + 1
    while (j < nums.length) {
      // 第三个数
      let second = 0 - nums[j] - first
      let third = nums[j]

      if(set.has(second)) {
        result.push([first, second, third])

        set.add(third)
        j++

        while (nums[j] === nums[j-1]) {j++} // 去重
      } else {
        set.add(third)
        j++
      }
    }
    set = new Set()
  }
  return result
};

    这里介绍另一种思路解法：排序 + 双指针

    为了防止结果数组中加入重复的元素，我们可以将 nums 进行排序，例如第一个数 nums[i] === nums[i-1] 时，nums[i] 作为第一个数与 nums[i-1] 作为第一个数得到的满足条件的三元组是一致的，所以此时 nums[i] 我们将不再进行判断，避免重复三元组，当然这只是第一个数，第二个数与第三个数的判断也是类似的。

    解题思路： 先数组排序，排序完后遍历数组，以 nums[i] 作为第一个数 first ，以 nums[i+1] 作为第二个数 second ，将 nums[nums.length - 1] 作为第三个数 last ，判断三数之和是否为 0 ，

    • <0 ，则 second 往后移动一位（nums 是增序排列），继续判断
    • >0 ，则 last 往前移动一位（nums 是增序排列），继续判断
    • ===0 ，则进入结果数组中，并且 second 往后移动一位， last 往前移动一位，继续判断下一个元组

    直至 second >= last 结束循环，此时， nums[i] 作为第一个数的所有满足条件的元组都已写入结果数组中了，继续遍历数组，直至 i === nums.length - 2 (后面需要有 second 、 last )

    代码实现：

    const threeSum = function(nums) {
    if(!nums || nums.length < 3) return []
    let result = [], second, last
    // 排序
    nums.sort((a, b) => a - b) 
    for (let i = 0; i < nums.length ; i++) {
        if(nums[i] > 0) break
        // 去重
        if(i > 0 && nums[i] === nums[i-1]) continue
        second = i + 1
        last = nums.length - 1
        while(second < last){
            const sum = nums[i] + nums[second] + nums[last]
            if(!sum){
                // sum 为 0
                result.push([nums[i], nums[second], nums[last]])
                // 去重
                while (second<last && nums[second] === nums[second+1]) second++ 
                while (second<last && nums[last] === nums[last-1]) last--
                second ++
                last --
            }
            else if (sum < 0) second ++
            else if (sum > 0) last --
        }
    }        
    return result
};

    leetcode

  5. thxiami commented on Apr 30, 2020

    @thxiami
    thxiami
    on Apr 30, 2020

    @sisterAn
    使用 Map() 的第一种方法, 也是可以通过排序来去重的.

    var threeSum = function (nums) {
  let set = new Set() // 使用 Set() 即可满足需求, 相对节省内存
  let result = []
  nums.sort((a, b) => (a - b))

  for(let i =0; i < nums.length - 2; i++) {
    while (nums[i] === nums[i - 1]) {i++} // 去重
    // 第一个数
    let first = nums[i]
    let j = i + 1
    while (j < nums.length) {
      // 第三个数
      let second = 0 - nums[j] - first
      let third = nums[j]

      if(set.has(second)) {
        result.push([first, second, third])

        set.add(third)
        j++

        while (nums[j] === nums[j-1]) {j++} // 去重
      } else {
        set.add(third)
        j++
      }
    }
    set = new Set()
  }
  return result
};
  6. sisterAn
    added
    腾讯
    LeetCode
    on May 5, 2020

  7. Been101 commented on Jul 11, 2020

    @Been101
    Been101
    on Jul 11, 2020
    const nums = [-1, 0, 1, 2, -1, -4]

const threeSum = (nums) => {
  const res = []
  nums = nums.sort((a, b) => a - b)

  for (let i = 0; i < nums.length - 2; i++) {
    const first = nums[i]
    if (first > 0) break
    if (i && nums[i] === nums[i - 1]) {
      continue
    }
    let l = i + 1
    let r = nums.length - 1
    while (l < r) {
      const sum = first + nums[l] + nums[r]
      if (sum === 0) {
        res.push([first, nums[l], nums[r]])
        l++
        r--
        while (l < r && nums[l] === nums[l - 1]) l++
        while (l < r && nums[r] === nums[r + 1]) r--
      }

      if (sum < 0) {
        let high = r
        let mid
        while (l <= high) {
          mid = Math.floor((l + high) / 2)
          if (first + nums[mid] < -nums[r]) {
            l = mid + 1
          } else if (first + nums[mid] > -nums[r]) {
            hight = mid - 1
          } else {
            l = mid
            break
          }
        }
        l++
      }
      if (sum > 0) {
        let low = l
        let mid
        while (low <= r) {
          mid = Math.floor((low + r) / 2)
          if (first + nums[mid] < -nums[l]) {
            low = mid + 1
          } else if (first + nums[mid] > -nums[l]) {
            r = mid - 1
          } else {
            r = mid
            break
          }
        }
        r-- 
      }
    }
  }

  return res
}

  8. Ha0ran2001 commented on May 28, 2022

    @Ha0ran2001
    Ha0ran2001
    on May 28, 2022
    const nums = [-1, 0, 1, 2, -1, -4]

const threeSum = (nums) => {
  const res = []
  nums = nums.sort((a, b) => a - b)

  for (let i = 0; i < nums.length - 2; i++) {
    const first = nums[i]
    if (first > 0) break
    if (i && nums[i] === nums[i - 1]) {
      continue
    }
    let l = i + 1
    let r = nums.length - 1
    while (l < r) {
      const sum = first + nums[l] + nums[r]
      if (sum === 0) {
        res.push([first, nums[l], nums[r]])
        l++
        r--
        while (l < r && nums[l] === nums[l - 1]) l++
        while (l < r && nums[r] === nums[r + 1]) r--
      }

      if (sum < 0) {
        let high = r
        let mid
        while (l <= high) {
          mid = Math.floor((l + high) / 2)
          if (first + nums[mid] < -nums[r]) {
            l = mid + 1
          } else if (first + nums[mid] > -nums[r]) {
            hight = mid - 1
          } else {
            l = mid
            break
          }
        }
        l++
      }
      if (sum > 0) {
        let low = l
        let mid
        while (low <= r) {
          mid = Math.floor((low + r) / 2)
          if (first + nums[mid] < -nums[l]) {
            low = mid + 1
          } else if (first + nums[mid] > -nums[l]) {
            r = mid - 1
          } else {
            r = mid
            break
          }
        }
        r-- 
      }
    }
  }

  return res
}

    你这个实现有问题

  9. XW666 commented on Jul 15, 2022

    @XW666
    XW666
    on Jul 15, 2022
     function threeSum(nums) {
    let arr = []
    nums.sort((a, b) => (a - b))
    for (let i = 0; i < nums.length - 2; i++) {
      let v1 = nums[i]
      //去重
      if (nums[i] === nums[i - 1]) {
        continue
      }
      for (let j = i + 1; j < nums.length; j++) {
        let v2 = nums[j]
        let v3 = 0 - v1 - v2

        if (nums.slice(j + 1).includes(v3)) {
          arr.push([v1, v2, v3])
        }
      }
    }

  }

  10. hanmaojiang commented on Nov 29, 2022

    @hanmaojiang
    hanmaojiang
    on Nov 29, 2022
    const nums = [-1, 0, 1, 2, -1, -4];

function threeSum(nums, res = [], sort = true) {
    if(!nums.length) return res;

    const arr = sort ? [...nums].sort() : nums;
    const sum = arr.pop();

    for(let i = 0; i< arr.length; i++) {
        const k = -sum - arr[i];

        if(arr.includes(k, i + 1)) {
            res.unshift([arr[i], k, sum]);
            break;
        }
    }

   return threeSum(arr, res, false);
}

threeSum(nums)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    LeetCode腾讯

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions