【Java 优选算法】双指针(下)

欢迎关注个人主页：逸狼

---

创造不易，可以点点赞吗~

如有错误，欢迎指出~

---

---

有效三角形的个数

题目链接

解法

解法1:暴力枚举--->O(n^3)

解法2:利用单调性,使用双指针来解决---->O(n^2)

1. 优化:对整个数组进行排序
2. 先固定最大数
3. 在最大数的左区间内,使用双指针算法,快速统计出符合要求的个数

统计分为两种情况:

• 能构成三角形的 a+b>c 
• 不能构成三角形的 a+b<=c 

画图举例

代码

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

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

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

题目链接

解法

解法一:暴力枚举,时间复杂度:O(n^2)--->超时

解法二:利用单调性,使用双指针算法解决,时间复杂度:O(n)

用sum表示两数相加的值,t表示目标值,无非就三种情况:

• sum<t  ---->left++
• sum>t  --->right--
• sum=t  ---->返回结果

注意:本题一定是有返回结果的,但为了照顾编译器,最后可以随意返回一个数组

画图举例

代码

class Solution {public int[] twoSum(int[] price, int target) {int sum=0,left=0,right=price.length-1;while(left<right){sum=price[left]+price[right];if(sum<target){left++;}else if(sum>target){right--;}else{return new int[]{price[left],price[right]};}}//照顾编译器return new int[]{0};}
}

三数之和

题目链接

解法

解法一:排序+暴力枚举+利用set去重, 时间复杂度:O(n^3)

解法二:排序+双指针

1. 排序
2. 固定一个数a
3. 在该数后面的区间内,利用"双指针算法"快速找到两个数的和等于 -a即可

处理细节问题:

• 去重
  1. 找到一种结果后,left和right指针要跳过重复的元素,
  2. 当使用完一次双指针算法之后,i也要跳过重复元素(细节1和2都要避免越界)
• 不漏
  • 找到一种结果之后,不要停,缩小区间,继续寻找

画图举例

代码

class Solution {public List<List<Integer>> threeSum(int[] nums) {Arrays.sort(nums);List<List<Integer>> ret=new ArrayList<>();int n=nums.length;for(int i = 0;i < n;){if(nums[i] > 0) break;int left=i+1,right =n-1,target=-nums[i];while(left < right){int sum=nums[left]+nums[right];if(sum > target) right--;else if(sum < target) left++;else{ret.add(new ArrayList<Integer>(Arrays.asList(nums[i],nums[left],nums[right])));left++;right--;//缩小区间,继续寻找//left,right去重while(left < right && nums[left] == nums[left-1]) left++;while(left < right && nums[right] == nums[right+1]) right--;}}i++;//i去重while(i < n && nums[i] ==nums[i-1]) i++;}return ret;}
}

四数之和

题目链接

解法

解法1:排序 + 暴力枚举 + 利用set去重

解法2: 排序 + 双指针(主要利用"三数之和"(上一题)的思路)

1. 依次固定一个数a;
2. 在a后面的区间内,利用"三数之和" 找到三个数,是这三个数等于target-a即可
   1. 依次固定一个数b
   2. 在b的后面的区间内,利用双指针找到两个数,是这两个数的和等于target-a-b即可

处理细节:

• 不重
• 不漏

画图举例

代码

class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {Arrays.sort(nums);List<List<Integer>> ret = new ArrayList<>();int n = nums.length;for(int i=0;i<n;){//固定数afor(int j=i+1;j<n;){//固定数bint left=j+1,right=n-1;long aim=(long)target-nums[i]-nums[j];//可能有溢出的风险,所以用longwhile(left<right){int sum = nums[left] + nums[right];if(sum > aim) right--;else if(sum < aim) left++;else{ret.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));left++; right--;//left 和 right 去重while(left < right && nums[left] == nums[left-1]) left++;while(left < right && nums[right] == nums[right+1]) right--;} }j++;//j去重while(j<n && nums[j] == nums[j-1]) j++;}i++;//i去重while(i<n && nums[i] == nums[i-1]) i++;}return ret;}
}