【优先算法】双指针 --（结合例题讲解解题思路）（C++）

目录

​编辑

1. 题目：三数之和

1.1算法思路 

1.2代码实现

 2.题目：四数之和

2.1算法思路

2.2代码实现

1. 题目：三数之和

力扣-三数之和

1.1算法思路 

方法一：暴力解法 

三层for循环，一个一个去找。因为有重复的，所以我们要将数据放进set，去重。

总结，这种方法，时间复杂度太高，如果用这个方法，难度根本没有，所以面试官想要的根本不是这种！！！

方法二：双指针

第一步，排好序 

第二步，固定一个数 a，因为题干说，三个数和==0，那么，我只需要在固定的这个数，的后面的区间利用“双指针”找到两个数，和== -a 即可。

当然，在过程中，我们需要特别注意的是，做到不重，不漏。

第三步，不漏

就是在left，right在移动过程中，找到了符合条件的之后，还要继续在区间查找。

第四步，不重

做到去重，就是每次找到符合条件的数，left++，right--，但是如果变化之后的数还是与之前的一样nums[left]==nums[left-1] 或者 nums[right]==nums[right+1]  此时，我们需要继续++或--

！！！但是注意，不要越界需要有限制条件left

1.2代码实现

暴力解法的代码实现，我这就不写了。双指针的解法思路也是有两种，例如下 方法一和方法二

 2.题目：四数之和

力扣-四数之和

2.1算法思路

四数之和算法思路和三数之和是一样的，唯一的差别就是，四数定了两个固定数（并不是完全固定的数哈！！！咱们脑子要灵活一点）

第一步，定第一个数 a=nums[i]

第二步，定第二个数 b=nums[x]

第三步，定left，right。（注意，{ a,b,nums[left],nums[right] }就是我们符合要求的数）

其余步骤也就和三数之和一样，做到，不重，不漏。唯一差别就是这里多了一步，b的去重。

2.2代码实现

本期学习到此结束，感谢大家支持！！！