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);
  1. 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.
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容