题目描述
给定n个整数的数组,找到元素a,b,c使得a + b + c = 0 。
For example, given array S = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
分析
- 注意n的取值范围，n的上限是多少？
- 优化：n^3 =>
- 利用双指针进行优化
3.1 利用双指针需要先对数组进行排序，获得数据阶梯特征
暴力解法
- 如何消除重复解
方法：先把目标三个数排序，之后利用HashSet排除重复数据
HashSet h=new HashSet(arr);
arr.clear();
arr.addAll(h);
- 3个循环
相对陌生知识点
- java获取当前系统时间：
- ArrayList使用（初始化、赋值、排除重复数据）
- List和ArrayList的转化
- 数组的排序
结果
- 第一次暴力求解超时了（Time Limit Exceeded），245 / 313 test cases passed.
- 第二次先排序，然后利用双指针进行优化，结果还是超时（ Time Limit Exceeded），311 / 313 test cases passed.
