3Sum Time Limit Exceeded HashMap 优化过程
2024-09-01 19:39:12
昨晚,在做leetcode上的3Sum题目时,感觉这道题目和2Sum很像,当时解决2Sum时,思路如下:
用HashMap的key存储 num[i],value存储下标 i,之后在遍历数组num时,判断target-num[i]是否在HashMap的key中,大致解题思路是这样的。于是我决定继续用这个思路解决3Sum问题。思路如下:
用2层for循环(同理4Sum问题用3层for循环),Java代码(此段代码Time Limit Exceeded)如下:
public List<List<Integer>> threeSum(int[] num) { Arrays.sort(num);
List<List<Integer>> listAll = new ArrayList<List<Integer>>();
Map<Integer, Integer> hm = new HashMap<Integer, Integer>();
for(int i = 0; i < num.length; i++) {
hm.put(num[i], i);
}
for (int i = 0; i < num.length; i++) {
int oneTmp = -num[i];
if (oneTmp < 0) {
break;
}
for (int j = i + 1; j < num.length; j++) {
int thirdTmp = oneTmp - num[j];
if (hm.containsKey(thirdTmp) && hm.get(thirdTmp) > j) {
List<Integer> listTmp = new ArrayList<Integer>();
listTmp.add(num[i]);
listTmp.add(num[j]);
listTmp.add(thirdTmp);
if (!listAll.contains(listTmp)) {
listAll.add(listTmp);
}
}
}
}
return listAll;
}
上面的这段代码提交时,一直显示Time Limit Exceeded。经过检查,发现问题出现在上面的红色代码处,我是计算了很多重复的triplet后,然后再用listAll的contains判断并去重,这样的操作会占用一定的时间,导致Time Limit Exceeded。
第一次优化:优化第二层for循环的下标j的遍历方法,Java代码(很奇怪的是这段代码第一次提交时Accepted了,之后几次提交都是Time Limit Exceeded)如下:
public List<List<Integer>> threeSum(int[] num) { Arrays.sort(num);
List<List<Integer>> listAll = new ArrayList<List<Integer>>();
Map<Integer, Integer> hm = new HashMap<Integer, Integer>();
for(int i = 0; i < num.length; i++) {
hm.put(num[i], i);
}
for (int i = 0; i < num.length; i++) {
int oneTmp = -num[i];
if (oneTmp < 0) {
break;
}
for (int j = i + 1; j < num.length; j++) {
int thirdTmp = oneTmp - num[j];
if (hm.containsKey(thirdTmp) && hm.get(thirdTmp) > j) {
List<Integer> listTmp = new ArrayList<Integer>();
listTmp.add(num[i]);
listTmp.add(num[j]);
listTmp.add(thirdTmp); listAll.add(listTmp);
while ((j < num.length - 1) && (num[j] == num[j + 1])) {
j ++;
}
}
}
}
return listAll;
}
其实就是把第一段代码中的红色部分,替换成黄色部分。
第二次优化,就是优化第一层for循环的下标 i 的遍历方法,最终Java代码(这次以318ms Accepted了)如下:
public List<List<Integer>> threeSum(int[] num) { Arrays.sort(num);
List<List<Integer>> listAll = new ArrayList<List<Integer>>();
Map<Integer, Integer> hm = new HashMap<Integer, Integer>();
for(int i = 0; i < num.length; i++) {
hm.put(num[i], i);
}
for (int i = 0; i < num.length; i++) {
int oneTmp = -num[i];
if (oneTmp < 0) {
break;
}
for (int j = i + 1; j < num.length; j++) {
int thirdTmp = oneTmp - num[j];
if (hm.containsKey(thirdTmp) && hm.get(thirdTmp) > j) {
List<Integer> listTmp = new ArrayList<Integer>();
listTmp.add(num[i]);
listTmp.add(num[j]);
listTmp.add(thirdTmp);
listAll.add(listTmp);
while ((j < num.length - 1) && (num[j] == num[j + 1])) {
j ++;
}
}
}
while ((i < num.length - 1) && (num[i] == num[i + 1])) {
i ++;
}
}
return listAll;
}
其实就是在第二段代码的基础上,再加上面绿色代码。至此,基于HashMap的解决3Sum问题的Java代码优化结束~
最新文章
- 关于jetty项目中的问题.
- varnish 的一个配置
- jquery提交表单,回调函数
- JavaScript的一些认识
- 《Java编程那点事儿》读书笔记(一)——基本数据结构
- c#线程的几种启动方法
- oc UIAlertController封装
- VPN工作原理
- Django ---- blog项目学习所得
- hdfs dfsadmin 命令详解
- Django开发Web监控工具-pyDash
- windows10下mysql8.0.11忘记密码的解决办法
- 51nod 1284 2 3 5 7的倍数 | 容斥原理
- Py修行路 内置模块补充 datetime模块
- restFull接口实现web
- POJ 2155 Matrix【二维树状数组+YY(区间计数)】
- LINQ学习笔记——(2)Lambda表达式
- 【网络流】【Dinic】【最大流】bzoj3396 [Usaco2009 Jan]Total flow 水流
- python实现进程的并发
- HTML5技巧