江苏龙网

  1. 首页 > 人文 > >

如何在数组中找到和为“特定值”的三个数？( 三 )


计算两指针对应元素之和 ， 5+6 = 11 ， 于是我们又找到符合要求的一组：
2 ， 5 ， 6
我们继续寻找 ， 让指针k左移：
如何在数组中找到和为“特定值”的三个数？文章插图
此时双指针又一次重合在一起 ， 我们结束本轮循环 。
按照这个思路 ， 我们一直遍历完整个数组 。
像这样利用两个指针指向数组两端 ， 不断向中间靠拢调整来寻找匹配组合的方法 ， 就是双指针法 ， 也被称为“夹逼法” 。
如何在数组中找到和为“特定值”的三个数？文章插图
如何在数组中找到和为“特定值”的三个数？文章插图
public static List> threeSumv2(int[] nums, int target) {Arrays.sort(nums);List> resultList = new ArrayList>();//大循环for (int i = 0; i < nums.length; i++) {int d = target - nums[i];// j和k双指针循环定位 ， j在左端 ， k在右端for (int j=i+1,k=nums.length-1; j list = Arrays.asList(nums[i], nums[j], nums[k]);resultList.add(list);}}}return resultList;}上面这段代码表面上有三层循环 ， 但每一轮指针j和k的移动次数加起来最多n-1次 ， 因此该解法的整体时间复杂度是O（n2） 。
最关键的是 ， 该解法并没有使用额外的集合（排序是直接在输入数组上进行的） ， 所以空间复杂度只有O（1）！
如何在数组中找到和为“特定值”的三个数？文章插图
如何在数组中找到和为“特定值”的三个数？文章插图


推荐阅读


上一篇：如何用 Python 进行 DeFi 应用的开发？

下一篇：小米集团 IoT 平台总经理部范典：技术创新是 AIoT 产业快速发展关键所在