015. 三数之和 | Leetcode题解

苏南

发布于 2020-12-16 15:06:52

4100

发布于 2020-12-16 15:06:52

文章被收录于专栏：漫画前端

点击上方“蓝色字体”，选择“设为星标”

每天复习一道面试题，轻松拿大厂Offer~

题目描述

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

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

示例：

给定数组 nums = \[-1, 0, 1, 2, -1, -4\]，

满足要求的三元组集合为：
\[
  \[-1, 0, 1\],
  \[-1, -1, 2\]
\]

难度：

难度：中等
支持语言：JavaScript、Python、C++

思路

采用分治的思想找出三个数相加等于 0，我们可以数组依次遍历，每一项 a[i]我们都认为它是最终能够用组成 0 中的一个数字，那么我们的目标就是找到剩下的元素（除 a[i]）两个相加等于-a[i].
通过上面的思路，我们的问题转化为了给定一个数组，找出其中两个相加等于给定值，我们成功将问题转换为了另外一道力扣的简单题目1. 两数之和。这个问题是比较简单的，我们只需要对数组进行排序，然后双指针解决即可。加上需要外层遍历依次数组，因此总的时间复杂度应该是 O(N^2)。
思路如图所示：

15.3-sum

在这里之所以要排序解决是因为，我们算法的瓶颈在这里不在于排序，而在于 O(N^2)，如果我们瓶颈是排序，就可以考虑别的方式了。

思路2

标签：数组遍历
首先对数组进行排序，排序后固定一个数 nums[i]nums[i]nums[i]，再使用左右指针指向 nums[i]nums[i]nums[i]后面的两端，数字分别为 nums[L]nums[L]nums[L] 和 nums[R]nums[R]nums[R]，计算三个数的和 sumsumsum 判断是否满足为 000，满足则添加进结果集
如果 nums[i]nums[i]nums[i]大于 000，则三数之和必然无法等于 000，结束循环
如果 nums[i]nums[i]nums[i] == nums[i−1]nums[i-1]nums[i−1]，则说明该数字重复，会导致结果重复，所以应该跳过
当 sumsumsum == 000 时，nums[L]nums[L]nums[L] == nums[L+1]nums[L+1]nums[L+1] 则会导致结果重复，应该跳过，L++L++L++
当 sumsumsum == 000 时，nums[R]nums[R]nums[R] == nums[R−1]nums[R-1]nums[R−1] 则会导致结果重复，应该跳过，R−−R--R−−
时间复杂度：O(n2)O(n^2)O(n2)，nnn 为数组长度

关键点解析

排序之后，用双指针
分治

复杂度分析

时间复杂度：
空间复杂度：取决于排序算法的空间消耗

代码

JavaScript 实现

/**
 * @来源：Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * @介绍：前端中文网是以前端进阶资源教程分享为主的专业网站，包括：前端、大厂面试题、typescript教程、程序人生、React.js
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function (nums) {
  if (nums.length < 3) return [];
  const list = [];
  nums.sort((a, b) => a - b);
  for (let i = 0; i < nums.length; i++) {
    //nums is sorted,so it's impossible to have a sum = 0
    if (nums[i] > 0) break;
    // skip duplicated result without set
    if (i > 0 && nums[i] === nums[i - 1]) continue;
    let left = i + 1;
    let right = nums.length - 1;

    // for each index i
    // we want to find the triplet [i, left, right] which sum to 0
    while (left < right) {
      // since left < right, and left > i, no need to compare i === left and i === right.
      if (nums[left] + nums[right] + nums[i] === 0) {
        list.push([nums[left], nums[right], nums[i]]);
        // skip duplicated result without set
        while (nums[left] === nums[left + 1]) {
          left++;
        }
        left++;
        // skip duplicated result without set
        while (nums[right] === nums[right - 1]) {
          right--;
        }
        right--;
        continue;
      } else if (nums[left] + nums[right] + nums[i] > 0) {
        right--;
      } else {
        left++;
      }
    }
  }
  return list;
};

  var twoSum = function(nums, target) {
    for (let i = 0; i < nums.length - 1; i++) { // 每个人
      for (let j = i + 1; j < nums.length; j++) { // 都去问其他的人
        if (nums[i]+nums[j] === target) {
          return [nums[i], nums[j]]
        }
      }
    }
  }

// 作者：wonderful611
// 链接：https://leetcode-cn.com/problems/3sum/solution/three-sum-ti-jie-by-wonderful611/

Java 实现

class Solution {
    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList();
        int len = nums.length;
        if(nums == null || len < 3) return ans;
        Arrays.sort(nums); // 排序
        for (int i = 0; i < len ; i++) {
            if(nums[i] > 0) break; // 如果当前数字大于0，则三数之和一定大于0，所以结束循环
            if(i > 0 && nums[i] == nums[i-1]) continue; // 去重
            int L = i+1;
            int R = len-1;
            while(L < R){
                int sum = nums[i] + nums[L] + nums[R];
                if(sum == 0){
                    ans.add(Arrays.asList(nums[i],nums[L],nums[R]));
                    while (L<R && nums[L] == nums[L+1]) L++; // 去重
                    while (L<R && nums[R] == nums[R-1]) R--; // 去重
                    L++;
                    R--;
                }
                else if (sum < 0) L++;
                else if (sum > 0) R--;
            }
        }
        return ans;
    }
}

//作者：guanpengchn
//链接：https://leetcode-cn.com/problems/3sum/solution/hua-jie-suan-fa-15-san-shu-zhi-he-by-guanpengchn/

C++ 实现

int len = nums.size();
for(int i=0; i<len-2; i++){
    for(int j=i+1; j<len-1;j++){
        for(int k=j+1; k<len; k++){
            if(nums[i] + nums[j] + nums[k] == 0){
                vector<int > vtemp{nums[i],nums[j],nums[k]};
                ret.push_back(vtemp);
            }
        }
    }
}

// 作者：edward_wang
// 链接：https://leetcode-cn.com/problems/3sum/solution/xiang-xi-jie-shi-shuang-zhi-zhen-jie-jue-san-shu-z/

Python 实现

思路

首先要熟悉求两数之和的写法，然后在 N > 2时，采用递归处理，一次减少1。
关键点是:
1. 先对nums排序；
2. 递归处理时的剪枝处理(参考注释)
这种写法参考了国际站上的文章，我觉得是最好的一种解法了。

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        if not nums: return []

        # 先排序，关键！
        nums.sort()
        ans = set()
        N, target = 3, 0
        self._find_sum(nums, 0, N, target, [], ans)
        return list(ans)

    def _find_sum(self, nums, start, N, target, path, ans):
        # terminator
        if len(nums) < N or N < 2: return
        # process
        if N == 2:
            # 两数求和
            d = set()
            for j in range(start, len(nums)):
                if target - nums[j] in d:
                    ans.add(tuple(path + [target - nums[j], nums[j]]))
                else:
                    d.add(nums[j])
        else:
            for i in range(start, len(nums)):
                # 剪枝1: target比剩余数字能组成的最小值还要小 或 比能组成的最大值还要大，就可以停止循环了
                if target < nums[i] * N or target > nums[-1] * N: break
                # 剪枝2: 去重
                if i > start and nums[i] == nums[i - 1]: continue
                # drill down
                self._find_sum(nums, i + 1, N - 1, target - nums[i], path + [nums[i]], ans)
        return

#作者：dz-lee
#链接：https://leetcode-cn.com/problems/3sum/solution/jian-ji-tong-yong-xie-fa-nshu-zhi-he-pythonxiang-x/

其他

原题leetcode链接：15.3sum - https://leetcode-cn.com/problems/3sum/](https://leetcode-cn.com/problems/3sum/)
合作方：JavaScript中文网 – 全球极客挚爱的技术成长平台
说明：leetcode 题解 | 每日一题? 所有题目并非全部为本人解答，部分为在复习学习中整理提取其他解题作者的优秀笔记，便于大家学习共同进步，如有侵权，请联系删除。

- 完 -

关注公众号「前端布道师」，做前端技术的传播者！

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2020-11-27，如有侵权请联系 cloudcommunity@tencent.com 删除

javascript