LeetCode热题100精讲——Top6:三数之和【双指针】

在这里插入图片描述

你好，我是安然无虞。

文章目录

- 题目背景
- 三数之和
- - C++解法
  - Python解法

题目背景

如果大家对于双指针的概念并不熟悉, 可以先看我之前为此专门写的算法详解:
蓝桥杯算法竞赛系列第七章——六道力扣经典带你刷爆双指针

这题其实还是一个专门的题型叫nSum, 感兴趣的老铁可以看之前的这篇文章, 后面不管遇到几数之和都可以按照这个套路解题:
蓝桥杯算法竞赛系列第十章·nSum问题的代码框架

三数之和

题目链接：三数之和

在这里插入图片描述

解题思路：

题目要求我们在数组nums中找到和为0的三个数，也就是说这里的n是3，target是0

其实说到底还是穷举，现在要求我们找到和为target的三个数，对于第一个数来说，nums数组中的所有数字都可能是，但是只要第一个数字确定了，剩下的两个数可以是什么呢？其实也就是和为target - nums[i]的两个数，这样一来，又回到了twoSum问题本身。

C++解法

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {// 先对数组进行排序sort(nums.begin(), nums.end());// 为了更好的复用，直接封装成为nSum函数return nSum(nums, 3, 0, 0);}vector<vector<int>> nSum(vector<int>& nums, int n, int start, int target){int sz = nums.size();vector<vector<int>> res;// 注意边界if(n < 2 || n > sz){return res;}if(n == 2){// 其实就是twoSum代码框架int left = start, right = sz - 1;while(left < right){int leftNum = nums[left], rightNum = nums[right];int sum = leftNum + rightNum;if(sum < target){left++;}else if(sum > target){right--;}else if(sum == target){res.push_back({leftNum, rightNum});while(left < right && leftNum == nums[left])left++;while(left < right && rightNum == nums[right])right--;}}}else{// n > 2的情况，递归计算(n-1)Sum的结果for(int i = start; i < sz; i++){// 也就是说，计算三数之和，先递归计算两数之和vector<vector<int>> twoNums = nSum(nums, n - 1, i + 1, target - nums[i]);// 将两数之和的结果加上当前的元素就是题目所求的三数之和for(auto twoNum : twoNums)  {// (n-1)Sum 加上 nums[i] 就是 nSumtwoNum.push_back(nums[i]);res.push_back(twoNum);}// 防止第一个元素重复while(i < sz - 1 && nums[i] == nums[i + 1]){i++;}}}return res;}
};

代码虽然看起来比较长，但是只要理解了就很简单，因为n==2时就是twoSum的双指针解法，n > 2时就是穷举第一个数字，然后递归计算(n-1)Sum，组长答案。

还有一点需要注意的是，类似 twoSum，3Sum 的结果也可能重复，比如输入是 nums = [1,1,1,2,3], target = 6，结果就会重复。

关键点在于，不能让第一个数重复，至于后面的两个数，我们复用的 twoSum 函数会保证它们不重复。所以代码中必须用一个 while 循环来保证 nSum 中第一个元素不重复。

Python解法

class Solution:def threeSum(self, nums: List[int]) -> List[List[int]]:nums.sort()# n 为 3，从 nums[0] 开始计算和为 0 的三元组return self.nSumTarget(nums, 3, 0, 0)# 注意：调用这个函数之前一定要先给 nums 排序# n 填写想求的是几数之和，start 从哪个索引开始计算（一般填 0），target 填想凑出的目标和def nSumTarget(self, nums: List[int], n: int, start: int, target: int) -> List[List[int]]:sz = len(nums)res = []# 至少是 2Sum，且数组大小不应该小于 nif n < 2 or sz < n:return res# 2Sum 是 base caseif n == 2:# 双指针那一套操作lo, hi = start, sz - 1while lo < hi:sum_val = nums[lo] + nums[hi]left, right = nums[lo], nums[hi]if sum_val < target:while lo < hi and nums[lo] == left:lo += 1elif sum_val > target:while lo < hi and nums[hi] == right:hi -= 1else:res.append([left, right])while lo < hi and nums[lo] == left:lo += 1while lo < hi and nums[hi] == right:hi -= 1else:# n > 2 时，递归计算 (n-1)Sum 的结果for i in range(start, sz):# Skip the duplicate element to avoid duplicate tripletif i > start and nums[i] == nums[i - 1]:continuesub = self.nSumTarget(nums, n - 1, i + 1, target - nums[i])for arr in sub:# (n-1)Sum 加上 nums[i] 就是 nSumarr.append(nums[i])res.append(arr)return res