611. 有效三角形的个数

目录

611. 有效三角形的个数

算法思路

算法代码

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

算法思路

 算法代码

HashSet

双指针

15. 三数之和

算法思路

算法代码 

18. 四数之和

​编辑算法思路

算法代码 

---

611. 有效三角形的个数

算法思路

 

算法代码

/*** 计算可能的三角形数量。** @param a 一个整数数组，数组中的元素代表三角形的边长。* @return 返回可能构成的三角形的数量。*/public int triangleNumber(int[] a) {// 如果数组为空，则无法构成任何三角形if(a.length==0) return 0;// 对数组进行排序，以便后续通过比较边长来判断是否可以构成三角形Arrays.sort(a);//给数组排序// 初始化计数器，用于记录可以构成的三角形的数量int count=0;// 用来计算三角形个数// 从最长的边开始检查，逐步减少边长，以找到所有可能的三角形组合int n= a.length-1;while(n>=2){// 使用双指针技术，左指针指向最短边，右指针指向最长边，中间的边长由数组排序决定int left=0;int right=n-1;while(left<right){// 如果当前选择的三条边满足构成三角形的条件，则增加计数器，并移动右指针// 如果a+b大于c，那么此时可以构成三角形，且在【left，right】内的所有情况都可以构成三角形//count+=right-left，right--if(a[left]+a[right]>a[n]){count+=right-left;right--;}else{// 如果不满足条件，则移动左指针，尝试其他可能的边长组合// 如果a+b小于c，那么此时无法构成三角形，让left++left++;}}// 检查完一组边长后，减少最长边的长度，继续检查下一组//当判断完后，让n--n--;}// 返回可以构成的三角形的总数量return count;}

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

算法思路

 

 算法代码

HashSet

 public int[] twoSum(int[] price, int target) {Set<Integer> set=new HashSet<>();int i=0;for(;i<price.length;i++){if(set.contains(target-price[i])){return new int[]{target-price[i],price[i]};}else{set.add(price[i]);}}return new int[]{-1,-1};}

双指针

/*** 使用双指针方法查找数组中两个数的和等于特定目标值的索引。* 这个方法避免了对每个可能的组合进行显式的迭代，通过调整左右指针来缩小搜索范围。** @param a 输入的整数数组。* @param target 目标值，我们需要找到两个数的和等于这个值。* @return 包含这两个数索引的数组。如果不存在这样的两个数，则返回{-1, -1}。*/public int[] twoSum(int[] a, int target) {// 初始化左指针为数组的起始位置// 利用双指针int left = 0;// 初始化右指针为数组的结束位置int right = a.length - 1;// 当左指针小于右指针时，执行循环while (left < right) {// 计算当前左右指针所指元素的和int sum = a[left] + a[right];// 如果和大于目标值，移动右指针，减小和if (sum > target) {right--;}// 如果和小于目标值，移动左指针，增大和else if (sum < target) {left++;}// 如果和等于目标值，返回当前左右指针的索引else {return new int[]{a[left], a[right]};}}// 如果没有找到合适的组合，返回{-1, -1}return new int[]{-1, -1};}

15. 三数之和

算法思路

算法代码 

    /*** 寻找数组中所有不重复的三元组，这些三元组的和为零。* * @param nums 输入的整数数组* @return 返回一个列表，包含所有和为零的不重复三元组*/public List<List<Integer>> threeSum(int[] nums) {// 初始化结果列表List<List<Integer>> res = new ArrayList<>();// 如果数组长度小于3，无法找到满足条件的三元组，直接返回空列表if (nums.length < 3) {return res;}// 初始化指针k，用于遍历数组int k = 0;// 遍历数组，直到k指向的元素后至少还有两个元素for (; k < nums.length - 2;) {// 初始化左指针left，指向k后的第一个元素int left = k + 1;// 初始化右指针right，指向数组最后一个元素int right = nums.length - 1;// 计算目标值，即要找到的三个数的和，这里取当前k指向的数的相反数int target = -nums[k];// 当左指针小于右指针时，进行循环while (left < right) {// 计算当前左指针和右指针指向的数的和int sum = nums[left] + nums[right];// 如果和大于目标值，说明右指针太靠右，需要向左移动if (sum > target) {right--;}// 如果和小于目标值，说明左指针太靠左，需要向右移动else if (sum < target) {left++;}// 如果和等于目标值，找到了一个满足条件的三元组else {// 将这个三元组添加到结果列表中res.add(Arrays.asList(nums[k], nums[left], nums[right]));// 移动左指针和右指针，继续寻找下一个满足条件的三元组left++;right--;// 跳过所有与当前左指针指向的数相同的元素，避免重复while (left < right && nums[left] == nums[left - 1]) {left++;}// 跳过所有与当前右指针指向的数相同的元素，避免重复while (left < right && nums[right] == nums[right + 1]) {right--;}}}// 移动k指针，继续寻找下一个可能的三元组k++;// 跳过所有与当前k指针指向的数相同的元素，避免重复while (k < nums.length - 2 && nums[k] == nums[k - 1]) {k++;}}// 返回结果列表return res;}

18. 四数之和

算法思路

考虑下面这种情况，我们需要给aim使用 long类型，并将target也强转为long

算法代码 

 /*** 寻找数组中所有不重复的四个数，使得它们的和等于指定的目标数。** @param nums 输入的整数数组。* @param target 目标和。* @return 返回一个列表，包含所有满足条件的四个数的组合。*/public List<List<Integer>> fourSum(int[] nums, int target) {List<List<Integer>> res = new ArrayList<>();// 如果数组长度小于4，无法找到四个数的组合，直接返回空结果if (nums.length < 4) {return res;}Arrays.sort(nums);// 双层循环遍历数组，第一层循环选择第一个数，第二层循环选择第二个数for(int t=0;t<nums.length-3;){for(int k=t+1;k<nums.length-2;){// 计算剩余两个数的目标和long aim=(long)target-nums[t]-nums[k];// 使用双指针法寻找剩余的两个数int left=k+1;int right=nums.length-1;// 当左指针小于右指针时，执行循环while(left<right){// 当前两个数的和int sum=nums[left]+nums[right];// 如果当前和小于目标和，左指针右移if(aim>sum) left++;// 如果当前和大于目标和，右指针左移else if(aim<sum) right--;// 如果当前和等于目标和，将四个数的组合添加到结果中else {res.add(Arrays.asList(nums[t],nums[k],nums[left],nums[right]));// 移动左指针和右指针，避免重复组合left++; right--;// 跳过所有与前一个数相同的数，避免重复组合while(left<right && nums[left]==nums[left-1]) left++;while(left<right && nums[right]==nums[right+1]) right--;}}// 移动第二个数的指针，避免重复组合k++;while(k<nums.length-2 && nums[k]==nums[k-1]) k++;}// 移动第一个数的指针，避免重复组合t++;while(t<nums.length-3 && nums[t]==nums[t-1]) t++;}return res;}

 以上就是双指针专题篇的内容，若有不足，欢迎指正~