长沙做网站最专业,wordpress 模板 含数据,上海网站建设中心,代账公司找往期文章包括但不限于本期文章中不懂的知识点#xff1a; 个人主页#xff1a;我要学编程(ಥ_ಥ)-CSDN博客 所属专栏#xff1a; 优选算法专题 想要了解双指针算法的介绍#xff0c;可以去看下面的博客#xff1a;双指针算法的介绍
目录
611.有效三角形的个数
LCR 1…找往期文章包括但不限于本期文章中不懂的知识点 个人主页我要学编程(ಥ_ಥ)-CSDN博客 所属专栏 优选算法专题 想要了解双指针算法的介绍可以去看下面的博客双指针算法的介绍
目录
611.有效三角形的个数
LCR 179.查找总价格为目标值的两个商品
15.三数之和
18. 四数之和 611.有效三角形的个数
题目 给定一个包含非负整数的数组 nums 返回其中可以组成三角形三条边的三元组个数。 示例 1: 输入: nums [2,2,3,4]
输出: 3
解释:有效的组合是:
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3示例 2: 输入: nums [4,2,3,4]
输出: 4提示: 1 nums.length 10000 nums[i] 1000 思路这个题目就是想让我们在给的数组中找出可以组成三角形的个数。确定三个数是否可以组成三角形任意两边之和大于第三边即可。
最简单的方法就是直接遍历数组根据三角形的判断条件暴力枚举即可。
代码实现
错误解法暴力枚举
class Solution {// 错误解法暴力枚举public int triangleNumber(int[] nums) {int count 0;// 注意这里的i,j,k的位置i最多只能倒带倒数第三个的位置,j....for (int i 0; i nums.length-3; i) {for (int j i1; j nums.length-2; j) {for (int k j1; k nums.length-1; k) {if (nums[i]nums[j] nums[k] nums[i]nums[k] nums[j] nums[k]nums[j] nums[i]) {count;}}}}return count;}
}
由于时间复杂度过高O(N^3)上面的代码肯定是跑不过的。
接下来就是想想怎么优化
我们知道三角形的判定还有一种简单方法两小边之和大于最大边即可。那怎么找两小边呢一个一个的去比较吗这个肯定不现实。其实Arrays这类中有一个静态方法可以用来对数字进行排序( sort() ) 知道了两小边之和就是找最大边进行判断即可。 这里我们就通过一定的条件来优化了第三层循环减少了循环的次数。
优化解法定位两小边 和 最大边进行比较
class Solution {// 优化解法一定位两小边 和 最大边进行比较public int triangleNumber(int[] nums) {Arrays.sort(nums);int count 0;for (int i 0; i nums.length-3; i) {for (int j i1; j nums.length-2; j) {// k此时是三个数中最大值的下标int k j1;while (k nums.length) {if (nums[i]nums[j] nums[k]) {count;k;} else {// 由于数组是升序因此后面的一定大于此时的值因此无需判断了break;}}}}return count;}
}
既然可以定位 两小边那么可不可以定位 最大边呢然后找两小边进行比较呢答案是可以的。 优化解法固定最大边比较另外两边
class Solution {// 优化解法二固定最大边比较另外两边public int triangleNumber(int[] nums) {Arrays.sort(nums);int count 0;for (int k nums.length-1; k 2; k--) {// 开始寻找两小边的范围值int i 0;int j k-1;while (i j) {if (nums[i]nums[j] nums[k]) {count (j-i); // 满足三角形的个数j--; // i变化没意义} else {i; // j变化没有意义}}}return count;}
}
注意在固定最大边的优化方法中我们只需要范围比较 nums[i] nums[j] 与 nums[k] 的大小关系即可。没有去一个一个的遍历比较 比较 nums[i] nums[j] 与 nums[k] 的大小关系。这就致使时间复杂度从 O(N^3) 降至 O(N^2)。
LCR 179.查找总价格为目标值的两个商品
题目 购物车内的商品价格按照升序记录于数组 price。请在购物车中找到两个商品的价格总和刚好是 target。若存在多种情况返回任一结果即可。 示例 1 输入price [3, 9, 12, 15], target 18
输出[3,15] 或者 [15,3]示例 2 输入price [8, 21, 27, 34, 52, 66], target 61
输出[27,34] 或者 [34,27] 提示 1 price.length 10^51 price[i] 10^61 target 2*10^6 思路 很简单的思路直接双层for循环遍历数组去找和target的值即可。
代码实现
错误解法暴力枚举
class Solution {// 错误解法暴力枚举public int[] twoSum(int[] price, int target) {int[] ret new int[2];for (int i 0; i price.length; i) {// 如果从j0开始的话就会有重复的且可能会出现ij的情况for (int j i1; j price.length; j) {if (price[i]price[j] target) {ret[0] price[i];ret[1] price[j];return ret;}}}return ret;}
}
上面的代码时间复杂度过高O(N^2)因此我们优化的方向就是降低时间复杂度为 O(N)。由于题目告诉我们了这个数组是有序的并且知道了要查找的数据因此我们可以对数据进行范围筛选。 通过上面的方法我们会发现查找的效率直线上升了。其思路的时间复杂度为 O(N)。
正确解法使用对撞指针减少查询的次数降低时间复杂度
class Solution {public int[] twoSum(int[] price, int target) {int[] ret new int[2];// 通过target的值来缩小范围遍历int left 0;int right price.length-1;while (left right) {if (price[left]price[right] target) {// 大于目标值得减小right--;} else if (price[left]price[right] target) {// 小于目标值。得增大left;} else {ret[0] price[left];ret[1] price[right];break;}}return ret;}
}
通过上面两个题目我们可以发现一个这样的规律对撞指针能降低一个幂次级的时间复杂度。
例如O(N^3) 使用对撞指针后可以降低为 O(N^2)O(N^2) 使用对撞指针后可以降低为 O(N)。当然最多也只能降低至 O(N)了不可能直接降为O(1)。
15.三数之和
题目 给你一个整数数组 nums 判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k 同时还满足 nums[i] nums[j] nums[k] 0 。请你返回所有和为 0 且不重复的三元组。 注意答案中不可以包含重复的三元组。 示例 1 输入nums [-1,0,1,2,-1,-4]
输出[[-1,-1,2],[-1,0,1]]
解释
nums[0] nums[1] nums[2] (-1) 0 1 0 。
nums[1] nums[2] nums[4] 0 1 (-1) 0 。
nums[0] nums[3] nums[4] (-1) 2 (-1) 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意输出的顺序和三元组的顺序并不重要。示例 2 输入nums [0,1,1]
输出[]
解释唯一可能的三元组和不为 0 。示例 3 输入nums [0,0,0]
输出[[0,0,0]]
解释唯一可能的三元组和为 0 。 提示 3 nums.length 3000-105 nums[i] 105 思路根据题目给出的信息来看我们要做的事情有两步第一找到符合三数之和为0的数第二对找到的数据进行去重操作。第一步的话首先想到的就是暴力枚举找到符合要求的数据。但是找到数据之后的去重操作是比较难的因为三个数的虽然总体是一样的但是其内部的顺序却不同我们无法直接判断因此这里我们就需要对数据进行排序操作。但问题又来了与其选择找出数据之后排序不如直接在原数组上面进行排序操作。可能有小伙伴会疑惑为什么要在原数组上进行排序呢如下图所示 排完序之后我们会发现重复的数据长得一模一样因此这里我们可以使用一个天然的去重容器set来处理最终得到的结果就是我们想要的答案。
代码实现
错误解法暴力枚举
class Solution {// 错误解法暴力枚举public ListListInteger threeSum(int[] nums) {ListListInteger list new ArrayList();// 1、先对数组整体排序Arrays.sort(nums);// 2、再去找符合条件的数据for (int i 0; i nums.length-3; i) {ListInteger sub_list new ArrayList();for (int j i1; j nums.length-2; j) {for (int k j1; k nums.length-1; k) {// 这里可以优化一点点效率0的话就直接跳出循环// 大于0再继续往后走也没用(根本不可能出现0的情况)if (nums[i]nums[j]nums[k] 0) {sub_list.add(nums[i]);sub_list.add(nums[j]);sub_list.add(nums[k]);ListInteger integerList new ArrayList(sub_list);list.add(integerList);// 每次插入数据之后要及时清空保证只有三个数据sub_list.clear();}}}}// 3、利用set对其去重SetListInteger set new HashSet();// 遍历list将其中的元素插入set中for (int i 0; i list.size(); i) {if (!set.contains(list.get(i))) {set.add(list.get(i));}}ListListInteger new_list new ArrayList();// 遍历set中的元素插入到new_listfor (ListInteger x : set) {new_list.add(x);}return new_list;}
}
注意上面代码的时间复杂度过大三层for循环两个遍历for循环 会超出时间限制。在最后一个将set中的元素插入new_list 中可能有的小伙伴会写出下面的代码。
for (int i 0; i list.size(); i) {if (set.contains(list.get(i))) {new_list.add(list.get(i));}
}
这个代码是有问题的没有达到去重的目的。因为 list 可能中存在着多份相同的数据但是在set 中只存在一份。因此当我们用 list 中的元素去遍历set 时就会出现重复的元素最终还是没有达到去重的效果。如下所示 优化的思路有两个1、对于查找数据时使用对撞指针来进行优化。即通过最外层循环来固定一个数然后再用对撞指针来找符合要求的数据。2、对去重的优化。set 去重虽然简单方便但是两个for循环也带来了不少时间上的消耗。
1、优化查找数据 正确解法对撞指针优化查找数据
class Solution {// 正确解法使用对撞指针降低时间复杂度public ListListInteger threeSum(int[] nums) {ListListInteger list new ArrayList();// 1、先对数组整体排序Arrays.sort(nums);// 2、再去找符合条件的数据for (int i 0; i nums.length-3; i) {ListInteger sub_list new ArrayList();int j i1;int k nums.length-1;while (j k) {if (nums[i]nums[j]nums[k] 0) {sub_list.add(nums[i]);sub_list.add(nums[j]);sub_list.add(nums[k]);ListInteger integerList new ArrayList(sub_list);list.add(integerList);sub_list.clear();// 只有一个增大另一个减小才可能达到相等// 这里如果不是两个同时走的话就会超出时间限制j; k--;} else if (nums[i]nums[j]nums[k] 0) {// 得减小k--k--;} else { // 0// 得增加jj;}}}// 3、利用set对其去重SetListInteger set new HashSet();// 遍历list将其中的元素插入set中for (int i 0; i list.size(); i) {if (!set.contains(list.get(i))) {set.add(list.get(i));}}ListListInteger new_list new ArrayList();// 遍历set中的元素插入到new_list中for (ListInteger x : set) {new_list.add(x);}return new_list;}
}
上面的代码虽然可以通过全部的测试用例但是时间效率非常之低。因此就要开始尝试看看能不能对去重操作进行优化。而最理想的优化就是能在找数据的同时去重。即在查找数据时不把重复的数据算入其中这就直接从源头上杜绝了去重的操作。那怎样才能找到不重复的数据呢
我们会发现一个规律当数据重复时结果一定是相同的。即找到一组符合要求的数据之后如果 j 对应的值 和 上一次 j 对应的值是一样的那么就可以跳过因为上一次 j 对应的值已经和其他值进行了结合检查。如果可以那么就成了一次重复的数据反之上一次也检查过了。同理k、i也是如此。当要注意一个数组越界问题。 class Solution {// 正确解法对撞指针查找去重public ListListInteger threeSum(int[] nums) {ListListInteger list new ArrayList();// 1、先对数组整体排序Arrays.sort(nums);// 2、再去找符合条件的数据for (int i 0; i nums.length-3; i) {// 与上一次的值相同就不需要再进行重复的操作了while (i-1 0 i nums.length-3 nums[i] nums[i-1]) {i;}// i对应的值一定是数组中最小的值如果它都0了那肯定找不到了while (i nums.length nums[i] 0) {i;}ListInteger sub_list new ArrayList();int j i1;int k nums.length-1;while (j k) {if (nums[i]nums[j]nums[k] 0) {sub_list.add(nums[i]);sub_list.add(nums[j]);sub_list.add(nums[k]);ListInteger integerList new ArrayList(sub_list);list.add(integerList);sub_list.clear();// 只有一个增大另一个减小才可能达到相等// 这里如果不是两个同时走的话就会超出时间限制j; k--;// 如果和上一次的数据相同则跳过while (j k nums[j] nums[j-1]) {j;}while (j k nums[k] nums[k1]) {k--;}} else if (nums[i]nums[j]nums[k] 0) {// 得减小k--k--;// 数据与上一次相同的话查找出来的还是同样的结果while (j k nums[k] nums[k1]) {k--;}} else { // 0// 得增加jj;// 数据与上一次相同的话查找出来的还是同样的结果while (j k nums[j] nums[j-1]) {j;}}}}return list;}
}
总的来说这一题还是比较难的。既要想要去重的方法利用set或者查找时排序相同的元素还要避免时间复杂度过高的情况下查找数据使用对撞指针进行优化处理。 接下来我们再来做一道与这个极其相似的题目。
18. 四数之和
题目 给你一个由 n 个整数组成的数组 nums 和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] 若两个四元组元素一一对应则认为两个四元组重复 0 a, b, c, d na、b、c 和 d 互不相同nums[a] nums[b] nums[c] nums[d] target 你可以按 任意顺序 返回答案 。 示例 1 输入nums [1,0,-1,0,-2,2], target 0
输出[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]示例 2 输入nums [2,2,2,2,2], target 8
输出[[2,2,2,2]] 提示 1 nums.length 200-109 nums[i] 109-109 target 109 思路和三数之和简直就是孪生兄弟。 同样是先排序再去查找数据这里只展示优化后的思路和解法想看推导过程和暴力枚举到优化的过程可见三数之和。
代码实现
错误解法用双层对撞指针代替四层for循环内部去重
class Solution {// 双层对撞指针会忽略一些数据public ListListInteger fourSum(int[] nums, int target) {ListListInteger list new ArrayList();Arrays.sort(nums);int i 0;int j nums.length-1;while (i j) {ListInteger sub_list new ArrayList();// 注意left和right的取值int left i1;int right j-1;while (left right) {// 注意对于内层循环来说只有left和right是可变化的i、j都是固定的if (nums[i]nums[j]nums[left]nums[right] target) {sub_list.add(nums[i]);sub_list.add(nums[j]);sub_list.add(nums[left]);sub_list.add(nums[right]);ListInteger integerList new ArrayList(sub_list);list.add(integerList);sub_list.clear();left;right--;while(left right nums[right] nums[right1]) {right--;}while(left right nums[left] nums[left-1]) {left;}} else if (nums[i]nums[j]nums[left]nums[right] target) {right--;while(left right nums[right] nums[right1]) {right--;}} else {left;while(left right nums[left] nums[left-1]) {left;}}}i;j--;while (i j nums[i] nums[i-1]) {i;}while (i j nums[j] nums[j1]) {j--;}}return list;}
}上面代码的思路确实不错的确可以减少不少时间的消耗但是会漏掉一些数据。
当 nums [-3, -1, 0, 2, 4, 5]、target 0时是找不到数据的。 感兴趣的小伙伴可以自己去测一测。原本我最先也是想到用这种方法来写感觉效率应该会很高但是后面经过调试发现根本就找不出来上面的数据。
正确解法使用双层for循环一层对撞指针查找数据时去重
class Solution {public ListListInteger fourSum(int[] nums, int target) {ListListInteger list new ArrayList();// 1、排序Arrays.sort(nums);// 2、开始找数据去重操作for (int i 0; i nums.length-4;) {for (int j i1; j nums.length-3;) {ListInteger sub_list new ArrayList();int left j1;int right nums.length-1;while (left right) {if (((long)nums[i]nums[j]nums[left]nums[right]) target) {sub_list.add(nums[i]);sub_list.add(nums[j]);sub_list.add(nums[left]);sub_list.add(nums[right]);ListInteger integerList new ArrayList(sub_list);list.add(integerList);sub_list.clear();left;right--;while(left right nums[right] nums[right1]) {right--;}while(left right nums[left] nums[left-1]) {left;}} else if ((long)nums[i]nums[j]nums[left]nums[right] target) {right--;while(left right nums[right] nums[right1]) {right--;}} else {left;while(left right nums[left] nums[left-1]) {left;}}}j;while (j nums.length-3 nums[j] nums[j-1]) {j;}}i;while (i 1 i nums.length-4 nums[i] nums[i-1]) {i;}}return list;}
}
注意
1、
因此我们在计算四数之和时强转为了 long类型。
2、
总体来说三数之和和四数之和还是有点难度的不仅需要编码能力强思路也要清新。
好啦本期 双指针算法专题2的学习之旅就到此结束啦我们下一期再一起学习吧
