15 三数之和,2021最新Android开发面试大全

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4],

满足要求的三元组集合为: [ [-1, 0, 1], [-1, -1, 2] ]

一. 暴力法,直接用三个指针遍历数组

public static List<List> threeSum(int[] nums)

{

Arrays.sort(nums); //数组排序

List<List> outList = new ArrayList<List>(); //定义一个ArrayList线性表

for (int i = 0; i < nums.length; i++)

{

if ((i > 0 && nums[i] == nums[i - 1])) //去重,做判断。如果符合条件就返回循环,对应的i直接跳过

continue;

for (int j = i + 1; j < nums.length; j++)

{

if ((j > i + 1 && nums[j] == nums[j - 1])) //去重

continue;

for (int k = j + 1; k < nums.length; k++)

{

if ((k > j + 1 && nums[k] == nums[k - 1])) //去重

continue;

if ((nums[i] + nums[j] + nums[k] == 0)) //判断和为零

{

outList.add(Arrays.asList(nums[i],nums[j],nums[k])); //添加到ArrayList中

break;

}

}

}

}

return outList; //返回找到的符合条件的数组

}

最终测试代码15 三数之和,2021最新Android开发面试大全

这时我们发现,超时了,这里的时间复杂度是O(n^3)。仔细分析我们知道循环太多了,而且都是三个for嵌套,这样直接导致了时间复杂度飙升。

那么我们想办法降低下时间复杂度。

二. 头尾指针法

方法一是三个指针依次数组后面移,那么我们试下头尾加指针,缩小范围来减小时间复杂度。

解题思路:

  1. 首先对数组进行排序,排序后固定一个数nums[i],再使用左右指针指向nums[i]后面的两端,数字分别为nums[L]和nums[R],计算三个数的和sum判断是否满足为0,满足则添加进结果集;

  2. 如果nums[i]大于0,则三数之和必然无法等于0,结束循环;

  3. 如果nums[i] == nums[i-1],则说明该数字重复,会导致结果重复,所以应该跳过;

  4. 当sum == 0时,nums[L] == nums[L+1]则会导致结果重复,应该跳过,L+ +;

  5. 当sum == 0时,nums[R] == nums[R-1]则会导致结果重复,应该跳过,R- -;

这里的时间复杂度是O(n^2),n为数组长度

public static List<List> threeSum(int[] nums) {

List<List> res = new ArrayList<>();

Arrays.sort(nums);

for (int i = 0; i + 2 < nums.length; i++)

{

写在最后

由于本文罗列的知识点是根据我自身总结出来的,并且由于本人水平有限,无法全部提及,欢迎大神们能补充~

将来我会对上面的知识点一个一个深入学习,也希望有童鞋跟我一起学习,一起进阶。

提升架构认知不是一蹴而就的,它离不开刻意学习和思考。

**这里,笔者分享一份从架构哲学的层面来剖析的视频及资料分享给大家,**梳理了多年的架构经验,筹备近1个月最新录制的,相信这份视频能给你带来不一样的启发、收获。

15 三数之和,2021最新Android开发面试大全

15 三数之和,2021最新Android开发面试大全

最近还在整理并复习一些Android基础知识点,有问题希望大家够指出,谢谢。

希望读到这的您能转发分享和关注一下我,以后还会更新技术干货,谢谢您的支持!

转发+点赞+关注,第一时间获取最新知识点

Android架构师之路很漫长,一起共勉吧!

最近还在整理并复习一些Android基础知识点,有问题希望大家够指出,谢谢。

希望读到这的您能转发分享和关注一下我,以后还会更新技术干货,谢谢您的支持!

转发+点赞+关注,第一时间获取最新知识点

Android架构师之路很漫长,一起共勉吧!

本文已被CODING开源项目:《Android学习笔记总结+移动架构视频+大厂面试真题+项目实战源码》收录

上一篇:西门子440变频器电路图 MM4307.5千瓦 MM440 15千瓦 电源驱动板图纸 有了这个15以下基本类似


下一篇:实验4-循环结构的嵌套:7-5 跟奥巴马一起画方块 (15 分)