双指针（二）双指针到底是怎么个事

一.有效的三角形个数

有效的三角形个数

class Solution {public int triangleNumber(int[] nums) {Arrays.sort(nums);int i=0,end = nums.length-1;int count = 0;for( i = end;i>=2;i--){int left = 0;int right = i-1;while(left<right){if(nums[left]+nums[right]>nums[i]){count+=right-left;right--;}else{left++;}}}return count;}}

解析：利用双指针和数组的单调性去解决本题。

如果一个数组为[2,3,2,5,4,9,10],求有效的三角形个数，最好的做法是先排序让数组有序慢慢找规律。

对于三角形来说判断三边能否构成三角形最主要的条件是：2边之和大于第三边。

设a<b<c，如果要能构成三角形那么必须满足以下三个等式：
等式一：a+b>c
等式二:a+c>b
等式三：b+c>a
现在已知c为最大数，对于等式二和等式三来说，一个最大的数在加上一个正数肯定大于另外一个数。所以在已知a,b,c三者的关系后，对于等式二和三是恒成立的。那么只需要看等式一即可：在a>b>c是如果a+b>c那么这三边就能构成三角形。对于本题数组要想知道任意三边的大小关系先排序。

数组有序后，每次挑选最末尾的元素当c,因为末尾的的元素有序后肯定是最大值。c确定后只需要找到a和b,满足a+b>c即可。设a为left，b为right,left和right在数组上移动去找满足left+right>c的元素，这就转换为双指针问题。

a+b>c且b和c固定不动让a动：如果left+right>c,2和9相加>10,说明这2个元素是满足条件一的。让left往后移动到下一个位置，right固定不动，left增大或者不变那么left+right>c是恒成立的。所以不需要再去移动，这个区间right-left所有值满足。总结这种过程就不需要自己再去计算，直接区间长度就是所有满足的条件。

a+b>c，a，c不动,b动：上面的例子说明在a+b>c的时候，b和c不动的情况下直接计算即可，回到刚刚的起点这次让a不动。

如果a+b>c,a固定，那么让b–即可，重新计算看是否满足条件。

现在left+right<c,left固定right无论怎么移动都满足left+right<c，不满足构成三角形的条件。所以只能left++找下一个是否满足。

当left和right相遇后c固定的每种情况都统计完毕，让c–继续重复计算。

总结如果暴力求解时间复杂度为o(n^3),用双指针加单调性时间复杂度为o(n*n)。

二.LCR 179. 查找总价格为目标值的两个商品

LCR 179. 查找总价格为目标值的两个商品

class Solution {public int[] twoSum(int[] price, int target) {int left=0;int right = price.length-1;int [] tmp = new int[2];while(left<right){if(price[left]+price[right]<target){left++;}else if(price[left]+price[right]>target){right--;}else{tmp[0]=price[left];tmp[1]=price[right];return tmp;}}return null;}
}

本题还是和上一题解法一样利用有序数组的单调性：
这是一种双指针的思想。首先，对数组price设定两个指针，一个指针left指向数组的起始位置（索引为0），另一个指针right指向数组的末尾位置（索引为price.length - 1）。然后，计算这两个指针所指向元素的和（price[left]+price[right]），并与目标值target进行比较。如果这个和小于目标值target，说明当前两数之和偏小，为了增大和的值，将左指针left向右移动一位，因为数组是有序的（虽然题中未明确提及数组有序，但从算法逻辑看是基于有序数组假设的），这样下一次计算的和可能会更接近目标值。
如果这个和大于目标值target，说明当前两数之和偏大，为了减小和的值，将右指针right向左移动一位，同理，下一次计算的和可能会更接近目标值。
不断重复这个过程，直到找到两数之和等于目标值target，此时将这两个数的索引（这里是值本身，按照代码逻辑）放入结果数组tmp并返回；如果在左指针left小于右指针right的情况下始终没有找到满足条件的两数之和等于目标值target，则返回null。

三.三数之和

三数之和

class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> list = new ArrayList<>();if(nums.length<3){return list;}Arrays.sort(nums);for(int i=0;i<nums.length-2;i++){if (i > 0 && nums[i] == nums[i - 1]) {continue;}int left = i+1;int right = nums.length-1;while(left<right){if(nums[left]+nums[right]<-nums[i]){left++;}else if(nums[left]+nums[right]>-nums[i]){right--;}else{list.add(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--;}}}}return list;}
}

题解：先排序可以更好去重。如果a+b+c=0,那么a+b=-c。所以只需要固定一个数充当c，定义2个指针去查找该指针对应下标元素的和等于-c的2个元素。

但是本题需要去重,[-1,1,1]和[1,-1,1]是一样的不能同时显示。
因为数组本来是排序后的，如果前一个元素和后一个元素一样时为了防止重复需要直接跳过，这样就能达到去重的效果。

整体思想是基于排序后的数组，通过固定一个数，然后使用双指针的方法来查找满足三数之和为0的组合。首先，对输入的数组nums进行排序。这一步是很关键的，因为排序后的数组可以让我们利用数组的单调性来进行高效的查找。然后，通过一个循环来固定第一个数（索引为i）。这里有一个优化点，如果当前的数和前一个数相同（即i > 0 && nums[i]==nums[i - 1]），就跳过这个数，以避免得到重复的结果。
对于固定的数nums[i]，设置两个指针left（初始化为i + 1）和right（初始化为数组的末尾nums.length - 1）。
计算nums[left]+nums[right]与-nums[i]的关系。如果nums[left]+nums[right] < -nums[i]，说明当前两数之和偏小，为了让和增大，将左指针left向右移动一位；如果nums[left]+nums[right] > -nums[i]，说明当前两数之和偏大，为了让和减小，将右指针right向左移动一位。
当nums[left]+nums[right]等于 - nums[i]时，就找到了一组满足三数之和为0的组合，将这三个数添加到结果列表list中。然后，为了避免重复结果，移动指针left和right跳过相同的数（通过内层的两个while循环）。
不断重复这个过程，直到left < right这个条件不满足为止。最后返回结果列表list，这个列表包含了所有满足三数之和为0的组合。

1. 假设使用上述threeSum函数对数组{-4, -1, -1, 0, 1, 2}进行操作的分析如下
   • 首先，数组被排序。排序后的数组为{-4, -1, -1, 0, 1, 2}。
   • 然后进入外层循环，i从0开始。
     • 当i = 0时，nums[i]= - 4。
       • 此时left = i+1 = 1，right = nums.length - 1=5。
       • 计算nums[left]+nums[right]与-nums[i]的关系。
       • 第一次比较时，nums[left]= - 1，nums[right]=2，nums[left]+nums[right]=1，-nums[i]=4。因为1 < 4，所以left指针右移，left变为2。
       • 此时nums[left]= - 1，nums[right]=2，nums[left]+nums[right]=1，仍然小于4，left继续右移变为3。
       • 此时nums[left]=0，nums[right]=2，nums[left]+nums[right]=2，小于4，left变为4。
       • 此时nums[left]=1，nums[right]=2，nums[left]+nums[right]=3，小于4，left变为5。
       • 此时left = right，这个i值下的内层循环结束。
     • 当i = 1时，nums[i]= - 1。
       • 由于i>0且nums[i]==nums[i - 1]，根据代码中的去重逻辑，这个i值被跳过。
     • 当i = 2时，nums[i]= - 1。
       • 此时left = i + 1=3，right = nums.length - 1 = 5。
       • 第一次比较时，nums[left]=0，nums[right]=2，nums[left]+nums[right]=2，-nums[i]=1，因为2>1，所以right指针左移，right变为4。
       • 此时nums[left]=0，nums[right]=1，nums[left]+nums[right]=1，等于1，找到一组解{-1, 0, 1}。然后按照去重逻辑，移动left和right指针跳过相同的数。
     • 当i = 3时，nums[i]=0。
       • 此时left = i+1 = 4，right = nums.length - 1=5。
       • 第一次比较时，nums[left]=1，nums[right]=2，nums[left]+nums[right]=3，-nums[i]=0，因为3>0，所以right指针左移，right变为4。
       • 此时left = right，这个i值下的内层循环结束。
     • 当i = 4时，nums[i]=1。
       • 此时left = i+1 = 5，right = nums.length - 1=5，left = right，这个i值下的内层循环结束。
     • 当i = 5时，i < nums.length - 2这个条件不满足，外层循环结束。
   • 最后，函数返回包含找到的满足三数之和为0的组合的列表，在这个例子中是[{-1, 0, 1}]。

1. 第一次去重（外层循环中的去重）

• 在for循环中，当i > 0 && nums[i]==nums[i - 1]时，会执行continue语句跳过当前循环。
  • 以数组{-4, -1, -1, 0, 1, 2}为例。
    当i = 0时，nums[i]= - 4，正常进行后续操作。
    当i = 1时，nums[i]= - 1，由于i>0且nums[i]==nums[i - 1]（因为nums[0]= - 4，nums[1]= - 1，此时nums[1]==nums[0]不成立，所以i = 1时正常进行内层循环操作）。
    -
    当i = 2时，nums[i]= - 1，此时i>0且nums[i]==nums[i - 1]（因为nums[1]= - 1，nums[2]= - 1），所以直接跳过i = 2这个情况的内层循环操作。这就避免了重复使用相同的第一个数来寻找三数之和为0的组合，因为如果不跳过，可能会得到重复的结果组合。
    2. 第二次去重（内层循环中的去重）
    当找到一组满足nums[left]+nums[right]== - nums[i]的解后，需要对left和right指针进行调整以避免重复结果。 例如，在找到一组解后，先执行left++;right---,然后，有两个while循环来进行去重。 对于while (left < right&&nums[left]==nums[left - 1])这个循环，它的目的是在找到一组解后，将left指针向右移动，跳过所有与当前left位置元素相同的元素。这是因为如果不跳过，下一次循环可能会得到相同的组合。例如，如果数组中有连续的相同元素，如{-1, -1, 0, 1, 2}，当找到{-1, 0, 1}这组解后，如果不跳过后面相同的-1，可能会再次得到{-1, 0, 1}这个组合。 同理，while (left < right&&nums[right]==nums[right + 1])这个循环是将right指针向左移动，跳过所有与当前right`位置元素相同的元素，以避免得到重复的结果组合。

四.四数之和

四数之和

class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {Arrays.sort(nums);List<List<Integer>> list = new ArrayList<>();for(int i=0;i<nums.length;){for(int j=i+1;j<nums.length;){int left = j+1;int right=nums.length-1;while(left<right){if((long)target-nums[i]-nums[j]>nums[left]+nums[right]){left++;}else if((long)target-nums[i]-nums[j]<nums[left]+nums[right]){right--;}else{list.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));left++;right--;while(left<right&&nums[left]==nums[left-1]){left++;}     while(left<right&&nums[right]==nums[right+1]){right--;}}}j++;while(j<nums.length&&nums[j]==nums[j-1]){j++;}}i++;while(i<nums.length&&nums[i]==nums[i-1]){i++;}}return list;}
}

本题还是和三数之和一样先排序在利用双指针求解。

三数之和是固定一个数然后求另外2个数是否为该数相反数。四数之和是固定2个数，目标值减去另外2个数的和是否等于固定的2个数的和。这里也是利用双指针。

相比于三数之和,三数之和只需要外部i去重，四数之和i和j都要去重。

1. 整体思想

• 这个fourSum方法的主要思想是在一个已排序的整数数组nums中找到四个数的组合，使得它们的和等于目标值target。
• 首先，对输入的数组nums进行排序。这是为了方便后续的操作，能够利用数组的单调性来优化查找过程。
• 然后，使用多层嵌套循环来确定四个数中的前两个数。
  • 外层for循环用于确定第一个数（索引为i），并且在每次循环中进行去重操作。如果当前的数和前一个数相同（即nums[i]==nums[i - 1]），就跳过这个数，以避免得到重复的结果。
    • 中层for循环用于确定第二个数（索引为j），同样在每次循环中进行去重操作。如果当前的数和前一个数相同（即nums[j]==nums[j - 1]），就跳过这个数。
• 内层while循环用于确定后两个数（索引为left和right）。
  • 在while循环中，计算target - nums[i]-nums[j]与nums[left]+nums[right]的关系。
  • 如果target - nums[i]-nums[j]>nums[left]+nums[right]，说明当前后两个数之和偏小，为了让和增大，将左指针left向右移动一位。
    • 如果target - nums[i]-nums[j]<nums[left]+nums[right]，说明当前后两个数之和偏大，为了让和减小，将右指针right向左移动一位。
      • 当target - nums[i]-nums[j]==nums[left]+nums[right]时，就找到了一组满足四数之和为target的组合，将这四个数添加到结果列表list中。然后，为了避免重复结果，移动指针left和right跳过相同的数（通过内层的两个while循环）。
      • 不断重复这个过程，直到所有可能的组合都被检查过，最后返回结果列表list，这个列表包含了所有满足四数之和为target的组合。

1. 第一次去重（外层循环中针对第一个数的去重）
   • 思想是在确定四数之和中的第一个数时，避免使用相同的数多次作为第一个数来构建组合。因为如果不进行去重，可能会得到重复的四数组合结果。例如，数组中有多个相同的数，若不处理，以这些相同数为第一个数构建的组合可能会重复。通过比较当前数与前一个数是否相同（在已经排序的数组中），如果相同就跳过当前数，从而保证每个不同的数作为第一个数只被使用一次来构建组合。
2. 第二次去重（中层循环中针对第二个数的去重）
   • 当确定了第一个数之后，在确定第二个数时进行去重。由于数组是排序的，在确定第二个数时，如果当前数和前一个数相同，那么以这个数为第二个数构建的四数组合会与之前以相同的第一个数和前一个相同的第二个数构建的组合重复。所以通过比较当前数（作为第二个数）与前一个数是否相同，相同则跳过，这样可以确保对于每个确定的第一个数，不同的第二个数只会被使用一次来构建组合，避免了重复的组合结果。
3. 第三次去重（内层循环中针对后两个数的去重）
   • 在找到一组满足四数之和为目标值的组合后，针对确定后两个数（left和right指向的数）的指针进行去重。当找到一组解后，如果不进行去重，下一次循环可能会因为left或者right指针没有移动到新的数而得到相同的组合。例如，数组中存在连续相同的数，在找到一组解后，如果left指针没有跳过相同的数，下一次循环可能会再次得到相同的组合。通过比较当前left（或right）指针指向的数与前一个（或后一个）数是否相同，相同则移动指针跳过，从而避免得到重复的组合结果。