【算法】【优选算法】双指针（下）

一、611.有效三⻆形的个数

题目链接：611.有效三⻆形的个数
题目描述：

题目解析：

• 返回能够成三角形的三元组合的个数；
• 三元组合内容相同，但是是原数组中不同的下标的元素，这样的三元组在这道题中是不相同的，要计数。

1.1 左右指针解法

解题思路：

• 因为我们能构成三角形的证明是两条最小边的和大于最大边，所以我们先将数组排序。
• 排序后，我们只需要固定一条边，然后使用左右指针在[0, 最大边）区间中去搜索符合条件的边即可。
• 固定的一条边必须是最大边，因为固定最大边的时候，要让另两边之和变大和变小只有一种走法（即变大左指针向后，变小右指针向前），如果固定最小边，让两边之差变小有两种走法（变小左指针向后和右指针向前都行）。
• 当左右指针元素和小于最大边，我们只需要将左指针向后走，让元素和更大即可。
• 当左右指针元素和大于最大边，现在[左指针，右指针) 中的元素和右指针的元素都可以构成三角形了。直接将其中元素个数添加到ret结果中，然后让右指针向前走，让元素和减小即可。

解题代码：

//时间复杂度O(n^2)
//空间复杂度O(logn)
import java.util.*;
class Solution {public int triangleNumber(int[] nums) {Arrays.sort(nums);int ret = 0;for(int i = nums.length - 1; i > 0; i--) {int left = 0;int right = i - 1;while(left < right) {if(nums[right] + nums[left] > nums[i]) {ret += right - left;right--;} else {left++;}}}return ret;}
}

1.2 暴力解法

解题思路：
直接使用三次for循环，将每一种构成三角形的可能都枚举出来，然后一一判断是否符合构成三角形的条件即可。但是这种方法时间复杂度过大，会超时。

解题代码：

//时间复杂度O(n^3)
//空间复杂度O(1)
import java.util.*;
class Solution {public int triangleNumber(int[] nums) {int ret = 0;int n = nums.length;for(int i = 0; i < n; i++) {for(int j = i +1 ; j < n; j++) {for(int k = j+1; k < n; k++) {if(nums[i] + nums[j] + nums[k] > 2 * Math.max(nums[i],Math.max(nums[j],nums[k]))) {ret++;}}}}return ret;}
}

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

题目链接：LCR 179.查找总价格为目标值的两个商品
题目描述：

题目解析：

• 数组是有序的，只需要找到一组数组中下标不同的两个数的和为target的返回该组合即可。

2.1 左右指针解法

解题思路：

• 因为数组是有序的，我们可以利用两数的和的单调性来解题。
• 我们初始左指针指向第一个元素，右指针指向最后一个元素。两个元素的和的单调性具有规律，让和变大让左指针向后移动，让和变小让右指针向前。

解题代码：

//时间复杂度O(n)
//空间复杂度O(1)
import java.util.*;
class Solution {public int[] twoSum(int[] price, int target) {int left = 0, right = price.length-1; while(left < right) {if(price[left] + price[right] > target) right--;else if(price[left] + price[right] < target) left++;else return new int[]{price[left],price[right]};}return null;}
}

2.2 暴力解法

解题思路：

• 我们直接使用两层for循环将不同的下标的两个元素的和枚举出来比较即可。
• 但是时间复杂度过大，会超出时间限制。
  解题代码：

//时间复杂度O(n^2)
//空间复杂度O(1)
import java.util.*;
class Solution {public int[] twoSum(int[] price, int target) {for(int i = 0; i < price.length; i++) {for(int j = 0; j < price.length; j++) {if(price[i] + price[j] == target) {return new int[]{price[i],price[j]};}}}return null;   }
}

三、15.三数之和

题目链接：15.三数之和
题目描述：

题目解析：

• 数组中三个元素和为0，并且要求其中的元素不能重合，对三元组中先后顺序也没有要求。

3.1 左右指针解法

解题思路：

• 当我们固定了一个数之后，是不是就是求另两个数的和等于这个固定的数的相反值，这就跟上一道题的思路差不多了，其实也跟第一题三角形思路也相似。
• 这道题给我们的数组是无序的，这样我们固定一个数之后，我们来求另两个数和时，单调性的控制就不是唯一的，所以我们要将数组排序。
• 我们使用一个for-i循环先固定一个数，然后使用左右指针在[i+1，nums.length-1] 区间中去三数之和等于0的数，然后将三元组放进结果集，并且左右指针同时移动一步；比0小就左指针向后走让和变大；比0大就右指针向前走。
• 去重思路：
• • 思路一：
• • • 在判断元素和前去重，由于我们数组是有序的，那么相同数值的元素肯定是在一起的，那么我们只要判断移动后的元素与前一步每移动时的值是否相同即可，当相同再次移动到不同即可。
• • • 但是这里面有细节问题：当我们使用这样的方法的时候，我们是直接将所有相同的直接跳过，所以我们有可能跳过初始值（也就是i == 0 left == i+1 right == nums.length-1），就如数组是这样[2, 2, 3 ,2]，当i = 0 时会跳过直接到第三个元素。所有在while循环条件要加上判断是初始值的条件
• • • 还有越界风险：所以在while判断的循环中还要将越界风险排除。
• • • 还有我们不知道出判断循环的原因是上面是哪个原因哪一个，所以我们在出来判断循环之后，还要判断是否已经越界或者不符合条件，也就是i >= nums.length 和 left >= right。
• • 思路二：
• • • 我们在判断和之后去重，只需要考虑越界风险，和相等即可。但是由于在判断和之中，我们要先将i++ 再去去重，去重后已经到了下一个要进循环的元素了, 所以我们for循环中就不要i++了。
• 小优化：在这道题中是判断和为0，所以我们当nums[i] > 0，后续[i+1，nums.length-1]空间都是正数，不可能还有结果了，直接出循环。

解题代码

//时间复杂度O(n^2)
//空间复杂度O(logn)
写法一：
import java.util.*;
class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> ret = new ArrayList<>();Arrays.sort(nums);int len = nums.length;for(int i = 0; i < len; i++) {if(nums[i] > 0) break;//对i去重while(i != 0 && i < len && nums[i] == nums[i - 1]) i++;if(i >= len) break;int left = i + 1;int right = len - 1;while(left < right) {while(left < right && left != i+1 && nums[left] == nums[left-1]) left++;//对left去重while(left < right && right != len-1 && nums[right] == nums[right+1]) right--;//对right去重if(left >= right) break;if(nums[left] + nums[right] < -nums[i]) left++;else if(nums[left] + nums[right] > -nums[i]) right--; else ret.add(Arrays.asList(nums[i],nums[left++],nums[right--]));}}return ret;}
}写法二：
import java.util.*;
class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> ret = new ArrayList<>();Arrays.sort(nums);int len = nums.length;for(int i = 0; i < len; ) {if(nums[i] > 0) break;int left = i + 1;int right = len - 1;while(left < right) {if(nums[left] + nums[right] < -nums[i]) left++;else if(nums[left] + nums[right] > -nums[i]) right--; else { ret.add(Arrays.asList(nums[i],nums[left++],nums[right--]));while(left < right && nums[left] == nums[left-1]) left++;//对left去重while(left < right && nums[right] == nums[right+1]) right--;//对right去重}}//对i去重i++;while(i < len && nums[i] == nums[i - 1]) i++;}return ret;}
}

3.2 暴力解法

解题思路：

• 我们直接使用三层for循环将每一个三元组枚举出来即可。
• 去重时我们直接使用HashSet这个集合类即可，所以我们要先将nums排序。
• 但是会超时。
  解题代码：

//时间复杂度O(n^3)
//空间复杂度O(logn)
import java.util.*;
class Solution {public List<List<Integer>> threeSum(int[] nums) {Arrays.sort(nums);List<List<Integer>> ret = new ArrayList<>();Set<List<Integer>> set = new HashSet<>();int len = nums.length;for(int i = 0; i < len; i++) {for(int j = i+1; j < len; j++) {for(int k = j+1; k < len; k++) {if(nums[i] + nums[j] + nums[k] == 0) {set.add(Arrays.asList(nums[i],nums[j],nums[k]));}}}}ret.addAll(set);return ret;}
}

四、18.四数之和

题目链接：18.四数之和
题目描述：

题目分析：
跟上面的三数之和，思路一样，代码雷同，只是需要固定两个数即可。

4.1 左右指针解法

解题思路：

• 思路参考上一道三数之和，两个细节：
• 这道题有例子是会超过int的最大值的，所以我们需要在计算和的时候使用long来储存。
  
  解题代码：

//时间复杂度O(n^3)
//空间复杂度O(logn)
写法一：
import java.util.*;
class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {Arrays.sort(nums);List<List<Integer>> ret = new ArrayList<>();int len = nums.length;for(int i = 0; i < len; i++) {//对i去重while(i < len && i != 0 && nums[i] == nums[i-1]) i++;if(i >= len ) break;for(int j = i+1; j < len; j++) {//对j去重while(j < len && j != i+1 && nums[j] == nums[j-1]) j++;if(j >= len ) break;long newTarget = (long)target - nums[i] - nums[j];int left = j + 1;int right = len - 1;while(left < right) {while(left < right && left != j+1 && nums[left] == nums[left-1]) left++;//对left去重while(left < right && right != len-1 && nums[right] == nums[right+1]) right--;//对right去重if(left >= right) break;long sum = (long)nums[left] + nums[right];if(sum > newTarget) right--;else if(sum < newTarget) left++;else ret.add(Arrays.asList(nums[i],nums[j],nums[left++],nums[right--]));}}}return ret;}
}
写法二：
import java.util.*;
class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {Arrays.sort(nums);List<List<Integer>> ret = new ArrayList<>();int len = nums.length;for(int i = 0; i < len;) {for(int j = i+1; j < len;) {long newTarget = (long)target - nums[i] - nums[j];int left = j + 1;int right = len - 1;while(left < right) {long sum = (long)nums[left] + nums[right];if(sum > newTarget) right--;else if(sum < newTarget) left++;else {ret.add(Arrays.asList(nums[i],nums[j],nums[left++],nums[right--]));while(left < right && nums[left] == nums[left-1]) left++;//对left去重while(left < right && nums[right] == nums[right+1]) right--;//对right去重}}//对j去重j++;while(j < len && nums[j] == nums[j-1]) j++;}i++;//对i去重while(i < len && nums[i] == nums[i-1]) i++;}return ret;}
}

4.2 暴力解法

解题思路：

• 4层for循环，HashSet去重。
• 会超时。

解题代码：

//时间复杂度O(n^4)
//空间复杂度O(logn)
import java.util.*;
class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {Arrays.sort(nums);List<List<Integer>> ret = new ArrayList<>();Set<List<Integer>> set = new HashSet<>();int len = nums.length;for(int i = 0; i < len; i++) {for(int j = i+1; j < len; j++) {for(int k = j+1; k < len; k++) {for(int n = k+1; n < len; n++){if((long)nums[i] + nums[j] + nums[k] + nums[n] == target) {set.add(Arrays.asList(nums[i],nums[j],nums[k],nums[n]));}}}}}ret.addAll(set);return ret;}
}