欢迎关注个人主页：逸狼
创造不易，可以点点赞吗~
如有错误，欢迎指出~
有效三角形的个数
题目链接
解法
解法1:暴力枚举--->O(n^3)
解法2:利用单调性,使用双指针来解决---->O(n^2)
优化:对整个数组进行排序先固定最大数在最大数的左区间内,使用双指针算法,快速统计出符合要求的个数统计分为两种情况:
能构成三角形的 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)
解法二:排序+双指针
排序固定一个数a在该数后面的区间内,利用"双指针算法"快速找到两个数的和等于 -a即可处理细节问题:
去重 找到一种结果后,left和right指针要跳过重复的元素,当使用完一次双指针算法之后,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: 排序 + 双指针(主要利用"三数之和"(上一题)的思路)
依次固定一个数a;在a后面的区间内,利用"三数之和" 找到三个数,是这三个数等于target-a即可 依次固定一个数b在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;){//固定数a for(int j=i+1;j<n;){//固定数b int left=j+1,right=n-1; long aim=(long)target-nums[i]-nums[j];//可能有溢出的风险,所以用long while(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; }}