【Leetcode】《双指针出击：多数和问题的“破阵之匙”，解锁高效算法密码》
前言
🌟🌟本期讲解关于双指针解决多数和问题~~~
🌈感兴趣的小伙伴看一看小编主页：GGBondlctrl-CSDN博客
🔥 你的点赞就是小编不断更新的最大动力
🎆那么废话不多说直接开整吧~~
目录
📚️1.和为s的两个数
1.1题目描述
本题的题目要求就是给定一个目标数，然后在数组内，找到两个数，使得这两个数的和为目标数；
题目展示如下：
很明显，就是找到两个数，然后等于目标数即可，此时的输出的顺序是不用过多担心的~~~
1.2题目解析
1.暴力枚举
思路：
这种做法就是直接两层for循环，直接开始遍历，然后直接相加，判断是否等于目标数，若等于直接拿出这两个数，反之遍历完了，还是没有，直接返回-1；
优点：快速，容易想到，直接上手，没有坑~~
缺点：时间复杂度比较高，效率降低~~~
具体的图片实例如下：
可以看到此时就是一个数一个数遍历，然后每次循环结束后，重上一个规定的数加1，再次继续循环遍历相加~~~
2.双指针
这里的思路就是通过利用双指针的思想进行操作，此时主要是利用题目的中的条件，即数组内的数字是顺序排序的；那么我们就可以利用这一点；
思路：
这里的思路就是：先规定一个两个指针子在数组的0号下标，一个在最后一个数字下标，注意了，由于数组是顺序排序的，那么当两个数和大于规定数，那么就移动右边的指针，使数字变小，由于左边已经是最小的了，那么就不应该移动，一旦移动就会变得更大；
具体到图示如下：
可以看到，此时由于两个数字之和大于目标数，那么就直接移动right指针，使和变小，若大于了目标数，那么就移动left，使两数之和整体变大；
总结：
得到的规律如下所示：
arr[left] + arr[rigth] > target：直接right--；
arr[left] + arr[rigth] < target：直接left++；
arr[left] + arr[rigth] == target：直接return；
那么以上就是本题的思路，以及图片展示，接下来就直接进行编写代码吧！！！
1.3题目代码
1.暴力枚举
这里就是通过两层for循环实现的，具体代码如下所示：
public static int[] TwoSum(int[] arr,int target){
//暴力枚举
for (int i = 0; i <arr.length-1 ; i++) {
for (int j = i+1; j < arr.length; j++) {
if(arr[i] + arr[j]==target){
return new int[]{arr[i],arr[j]};
}
}
}
return new int[]{-1};
}解释：
1.注意本题的放回的格式，是一个数组的对象；
2.这里的规定的数字之后，内层循环始终都是从外层循环的后一个开始遍历的，因为遍历过后的数字不必再次循环遍历并判断了；
时间复杂度： 由于两层for循环，那么这里的时间复杂度很明显就是O（n^2）
2.双指针
具体的代码如下所示：
public static int[] TwoSum_Double(int[] arr,int target){
//双指针算法
int left=0;
int right=arr.length-1;
while (right>left){
if (arr[right] + arr[left] > target) {
right--;
}else if(arr[right] + arr[left] < target){
left++;
}else {
return new int[]{arr[left],arr[right]};
}
}
return new int[]{-1};
}解释：
这里的代码就是通过上述的思路分析进行编写的，根据不同的情况进行操作，大于目标数直接right--，小于目标数直接left++，等于目标数直接返回这两个数，这里要注意截止的情况就是right小于left的情况；
时间复杂度：这里由于在本数组中进行操作，没有嵌套其他循环，那么时间复杂度：O（n）
📚️2.三数之和
2.1题目描述
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。得到
注意：答案中不可以包含重复的三元组。
具体的输出用例如下所示：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。
当然这里还要考虑没有合适的三个数的情况；
2.2题目解析
1.暴力枚举
这里我们要注意，在判断三个数和后，由存在可能重复的情况，所以这里我们进行每个得出的数组的排序，但是这里我们可以在开始时，直接将数组进行排序，得出的可以得到两个完全相同的数组，此时我们就可以使用hashset进行去重的操作；
具体的情况就是如下的：
解释：
此时就会发现，当排序后我们的目标数组就是一样的，那么此时就可以使用hashset进行去重的操作了；
优点：容易想到，代码实现简单；
缺点：时间复杂度太高，为O（n^3），那么此时在力扣运行后肯定是超出时间限制了；
2.双指针
此时我们可以如下思路所示：
由于是要取出三个数字，那么此时规定一个数然后定义两个数，但是此时由于规定的数后，此时其余的两个数字的和肯定是这个数的相反数，那么此时就变成了：
规定一个数，其余两个数之和为这个数的相反数；
这个不就是上面求两数和为s的变种题目吗！！！
此时我们的图示就是如下所示的：
此时我们发现这不就是我们两数求和为某个数的操作吗？
第二个问题：
这里的去重也可以使用上述的hashset的方式，但是这里还有一种办法，就是每个指针找到目标的两个数后，继续移动， 这里就是一个重要的点，此时若移动后的数，和之前的数是一样的，那么此时就可以直接跳过
如下所示：
那么此时发现一样的就继续移动，知道不为一样的为止，那么就要子啊每次找到目标的两个数字后，就要进行去重的判断
注意：一个大循环规定数，这个也要进行去重的操作；
第三个问题：
此时假如一个特殊的数组，存在后，那么这种情况下就要进行边界判断；由于每次符合前一个数等于后面一个数，（去重操作导致）就会出现越界的情况，此时也要进行判断；
2.3题目代码
小编这里只演示双指针的算法，此时大家可以试试暴力枚举的算法，当然此时放在leetcode上肯定是超时的~~~
代码如下：
public List<List<Integer>> threeSum(int[] nums) {
//双指针算法，规定一个数，其他两数之和为这个数的相反数，和两数和为s的思想基本一致
//规定放回的形式
//先将数组进行排序的操作；
Arrays.sort(nums);
List<List<Integer>> ret = new ArrayList<>();
for (int i = 0; i < nums.length; ) {
if (nums[i] > 0) {
break;
}
int left = i + 1;
int right = nums.length - 1;
int target = -nums[i];//目标相加的和的数解释：
此时就是进行数组的重排序，然后规定放回的对象类型；
进行优化：由于确定一个数后，后面两个数和为它的相反数，若这个规定数大于0，说明后面的数更大，就不可能为它的相反数即负数；
然后规定每个指针下标；
List<List<Integer>> ret = new ArrayList<>();
for (int i = 0; i < nums.length; ) {
if (nums[i] > 0) {
break;
}
int left = i + 1;
int right = nums.length - 1;
int target = -nums[i];//目标相加的和的数
//这里就进行目标数的相加算法
while (left < right) {
if (nums[left] + nums[right] > target) {
right--;
} else if (nums[left] + nums[right] < target) {
left++;
} else {
ret.add(new ArrayList<>(Arrays.asList(nums[i], nums[left], nums[right])));
//这里要进行去重的操作
left++;
right--;
while (left < right && nums[left] == nums[left - 1] ) {
left++;
}
while (left < right && nums[right] == nums[right + 1] ) {
right--;
}//此时可能会发生越界的问题
}
}解释：
这里就是通过上述两数和的问题的格式基本一致，但是在确定返回的数后，要进行对应的指针操作，并添加到规定的对象里；注意由于存在越界的问题，假如如下数据：
此时就会出现一直跳，跳出数组范围，所以得规定条件；
注意：
在提供条件的时候，首先得判断这里的指针的范围，不能先判断是否等于前一个数字；
这里的所谓的前一个数据：right这里前一个数据就是right++，left的前一个数据就是left--；
i++;//解决i重复的问题
while (i<nums.length && nums[i] == nums[i - 1]) {
i++;
}
}
return ret;解释：
最后就是规定的数字必须去重，这里的去重的操作和上面的操作基本是一致的，必须是首先判断指针的的范围；然后再判断是否等于前一个数；
📚️3.总结
本期小编主要讲解了leetcode两道双指针比较重要的题目，就是“和为s的两个数”与“三数之和”；当然这里主要还是大家在看完题解后，能自己敲代码~~~
🌅🌅🌅~~~~最后希望与诸君共勉，共同进步！！！
💪💪💪以上就是本期内容了， 感兴趣的话，就关注小编吧。
😊😊 期待你的关注~~~
原文地址：https://blog.csdn.net/GGBond778/article/details/144217907
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！