延吉网站建设公司,本地丹阳网站建设,免费建网站平台,望城经济建设开区门户网站欢迎关注个人主页#xff1a;逸狼 创造不易#xff0c;可以点点赞吗~ 如有错误#xff0c;欢迎指出~ 有效三角形的个数
题目链接
解法
解法1:暴力枚举---O(n^3)
解法2:利用单调性,使用双指针来解决----O(n^2)
优化:对整个数组进行排序先固定最大数在最大数的左… 欢迎关注个人主页逸狼 创造不易可以点点赞吗~ 如有错误欢迎指出~ 有效三角形的个数
题目链接
解法
解法1:暴力枚举---O(n^3)
解法2:利用单调性,使用双指针来解决----O(n^2)
优化:对整个数组进行排序先固定最大数在最大数的左区间内,使用双指针算法,快速统计出符合要求的个数
统计分为两种情况:
能构成三角形的 abc 不能构成三角形的 abc
画图举例 代码
class Solution {public int triangleNumber(int[] nums) {Arrays.sort(nums);int n0,inums.length-1;while(i2){int left0,righti-1;while(leftright){ 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 ret0,nnums.length;for(int i n-1;i2;i--){int left0,righti-1;while(leftright){if(nums[left]nums[right]nums[i]){ret(right-left);right--;}else{left;}}}return ret;}
} 查找总价格为目标值的两个商品
题目链接 解法
解法一:暴力枚举,时间复杂度:O(n^2)---超时
解法二:利用单调性,使用双指针算法解决,时间复杂度:O(n)
用sum表示两数相加的值,t表示目标值,无非就三种情况:
sumt ----leftsumt ---right--sumt ----返回结果
注意:本题一定是有返回结果的,但为了照顾编译器,最后可以随意返回一个数组
画图举例 代码
class Solution {public int[] twoSum(int[] price, int target) {int sum0,left0,rightprice.length-1;while(leftright){sumprice[left]price[right];if(sumtarget){left;}else if(sumtarget){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 ListListInteger threeSum(int[] nums) {Arrays.sort(nums);ListListInteger retnew ArrayList();int nnums.length;for(int i 0;i n;){if(nums[i] 0) break;int lefti1,right n-1,target-nums[i];while(left right){int sumnums[left]nums[right];if(sum target) right--;else if(sum target) left;else{ret.add(new ArrayListInteger(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[right1]) 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 ListListInteger fourSum(int[] nums, int target) {Arrays.sort(nums);ListListInteger ret new ArrayList();int n nums.length;for(int i0;in;){//固定数afor(int ji1;jn;){//固定数bint leftj1,rightn-1;long aim(long)target-nums[i]-nums[j];//可能有溢出的风险,所以用longwhile(leftright){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[right1]) right--;} }j;//j去重while(jn nums[j] nums[j-1]) j;}i;//i去重while(in nums[i] nums[i-1]) i;}return ret;}
}
