OJ-leetcode-15. 三数之和(中等双指针)

系统管理员 2022-12-12 04:48 103阅读 0赞

**目录**

题目

思路

代码

结果

优秀题解

提升笔记

全部代码

--------------------

# 题目 #

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

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

示例：

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

满足要求的三元组集合为：  
\[  
  \[-1, 0, 1\],  
  \[-1, -1, 2\]  
\]  
链接：https://leetcode-cn.com/problems/3sum

# 思路 #

看示例可以看出，排序后比较合适。可以方便剪枝和去重。我们先排序，然后固定第一个数num\[i\]，遍历一遍即可。

然后定义两个指针（下标），从i后面一个left=i+1向右，从最后一个right=len-1向左进行逼近。

left<right，若三数之和sums<0，那么向右移动left使三数之和增大，若sums>0，向左移动right使sums减小。相等时保存结果。

left>=right，继续下一个num\[i\]。

剪枝：由于nums\[i\]<nums\[left\]<nums\[right\]，如果nums\[i\]>0，那么两个指针怎么移动也不可能找到了。

我就写了上面的一个剪枝，当然如果nums\[i\]+nums\[left\]>0，right怎么移动也不可能找到了。

去重：由于已经排好序，若某个数字移动时相同就是重复三元组。例如，-4 \-1 \-1 0 1 2 ，三个标红的和为0，若移动第一个数一次，那么后序两个指针也会移动到0 1，-4\-1 \-1 0 1 2，这样的三元组便是重复的，所以去重就是若相等继续后移。

## 代码 ##

// 双指针法
    class Solution {
    public:
    	vector<vector<int>> three(vector<int>& nums,int target) {
    		vector<vector<int>> ans;
    		int len = nums.size();
    		if (len < 3)return ans;
    		sort(nums.begin(),nums.end());
    		for (int i=0;i<len;++i)
    		{
    			if (nums[i] > target) break; // 剪枝：若第一个最小的数都大于target，就没必要从后面逼近选了
    			if (i > 0 && nums[i] == nums[i - 1])continue; //去重
    			int left = i + 1; //左指针
    			int right = len - 1;//右指针
    			//左右逼近
    			while (left<right)
    			{	
    				int sums = nums[i] + nums[left] + nums[right];
    				//cout<< nums[i] <<" "<<nums[left]<<" "<<nums[right]<<" "<<sums<<endl;
    				//cout << left << " " << right << endl;
    				if (sums == target)
    				{
    					vector<int> res;
    					res.emplace_back(nums[i]);
    					res.emplace_back(nums[left]);
    					res.emplace_back(nums[right]);
    					ans.emplace_back(res);
    					while (left < right&&nums[left] == nums[left+1])++left;//去重右移
    					++left;
    					while (left < right&&nums[right] == nums[right-1])--right;//去重左移
    					--right;
    				}
    				else if (sums < target)++left;
    				else --right;
    			}
    		}
    		return ans;
    	}
    	vector<vector<int>> threeSum(vector<int>& nums) {
    		return three(nums, 0);
    	}
    };

## 结果 ##

![20201006100156916.PNG][] 结果

# 优秀题解 #

[大力王-简洁代码][-]

> class Solution \{  
> public:  
>     vector<vector<int>> threeSum(vector<int>& nums) \{  
>         sort(nums.begin(), nums.end());  
>         int N = nums.size();  
>         vector<vector<int> > res;  
>         for (int i = 0; i < N - 2; ++i) \{  
>             if (nums\[i\] > 0) break;  
>             if (i > 0 && nums\[i\] == nums\[i - 1\]) continue;  
>             int l = i + 1;  
>             int r = N - 1;  
>             while (l < r) \{  
>                 int s = nums\[i\] + nums\[l\] + nums\[r\];  
>                 if (s > 0) \{  
>                     --r;  
>                 \} else if (s < 0) \{  
>                     ++l;  
>                 \} else \{  
>                     res.push\_back(\{nums\[i\], nums\[l\], nums\[r\]\});  
>                     while (l < r && nums\[l\] == nums\[++l\]);  
>                     while (l < r && nums\[r\] == nums\[--r\]);  
>                 \}  
>             \}  
>         \}  
>         return res;  
>     \}  
> \};

99.97%，可能不太准，但人家代码确实写得更简洁，值得学习。

# 提升笔记 #

1.push\_back(\{nums\[i\], nums\[l\], nums\[r\]\})，对于小的vector放入大的vector没必要再定义一个了，直接这样花括号。

2.nums\[l\] == nums\[++l\]，先+1再比较，可以使代码更简洁。

# 全部代码 #

//https://leetcode-cn.com/problems/3sum/
    /*
    Project:15. 三数之和
    Date:    2020/09/
    Author:  Frank Yu
    不重复指的是元组间不重复，不是元组内的数字不可重复
    */
    #include<vector>
    #include<algorithm>
    #include<iostream>
    using namespace std;
    void check(vector<vector<int>> ans)
    {
    	cout << "元组为" << endl;
    	for (auto nums:ans)
    	{
    		for (auto num : nums)
    		{
    			cout << num << " ";
    		}
    		cout << endl;
    	}
    }
    // 双指针法
    class Solution {
    public:
    	vector<vector<int>> three(vector<int>& nums,int target) {
    		vector<vector<int>> ans;
    		int len = nums.size();
    		if (len < 3)return ans;
    		sort(nums.begin(),nums.end());
    		for (int i=0;i<len;++i)
    		{
    			if (nums[i] > target) break; // 剪枝：若第一个最小的数都大于target，就没必要从后面逼近选了
    			if (i > 0 && nums[i] == nums[i - 1])continue; //去重
    			int left = i + 1; //左指针
    			int right = len - 1;//右指针
    			//左右逼近
    			while (left<right)
    			{	
    				int sums = nums[i] + nums[left] + nums[right];
    				cout<< nums[i] <<" "<<nums[left]<<" "<<nums[right]<<" "<<sums<<endl;
    				//cout << left << " " << right << endl;
    				if (sums == target)
    				{
    					vector<int> res;
    					res.emplace_back(nums[i]);
    					res.emplace_back(nums[left]);
    					res.emplace_back(nums[right]);
    					ans.emplace_back(res);
    					while (left < right&&nums[left] == nums[left+1])++left;//去重右移
    					++left;
    					while (left < right&&nums[right] == nums[right-1])--right;//去重左移
    					--right;
    				}
    				else if (sums < target)++left;
    				else --right;
    			}
    		}
    		return ans;
    	}
    	vector<vector<int>> threeSum(vector<int>& nums) {
    		return three(nums, 0);
    	}
    };
    //主函数
    int main()
    {
    	vector<int> nums{ -1, 0, 1, 2, -1, -4 };
    	//vector<int> nums{ 0, 0, 0, 0, 0, 0 };
    	//vector<int> nums{1,0};
    	Solution s;
    	check(s.threeSum(nums));
    	return 0;
    }

更多内容：[OJ网站题目分类，分难度整理笔记（leetcode、牛客网）][OJ_leetcode]

喜欢本文的请动动小手点个赞，收藏一下，有问题请下方评论，转载请注明出处，并附有原文链接，谢谢！如有侵权，请及时联系。如果您感觉有所收获，自愿打赏，可选择支付宝18833895206（小于），您的支持是我不断更新的动力。

[20201006100156916.PNG]: /images/20221123/3b69871220454b159294aa8c92628c14.png
[-]: https://leetcode-cn.com/problems/3sum/solution/c-can-kao-ge-lu-shen-xian-de-jie-fa-by-da-li-wang/
[OJ_leetcode]: https://blog.csdn.net/lady_killer9/article/details/108273799