15. 3Sum

题目描述

给定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]
]

分析

1. 注意n的取值范围，n的上限是多少？
2. 优化：n^3 =>
3. 利用双指针进行优化
   3.1 利用双指针需要先对数组进行排序，获得数据阶梯特征

暴力解法

1. 如何消除重复解
   方法：先把目标三个数排序，之后利用HashSet排除重复数据

HashSet h=new HashSet(arr);
arr.clear();
arr.addAll(h);

2. 3个循环

相对陌生知识点

1. java获取当前系统时间：
2. ArrayList使用（初始化、赋值、排除重复数据）
3. List和ArrayList的转化
4. 数组的排序

结果

1. 第一次暴力求解超时了（Time Limit Exceeded），245 / 313 test cases passed.
2. 第二次先排序，然后利用双指针进行优化，结果还是超时（ Time Limit Exceeded），311 / 313 test cases passed.