一直没看清英文题目,导致各种WA!唉唉唉。。。
通过Judge Small后:
尝试O(N2)算法
最后在stackoverflow上找到了答案 唉
http://stackoverflow.com/questions/10732522/difference-between-two-similar-algorithms-of-3sum
第二天想了一下,发现其实还是三重循环,k其实就是j里面的一层循环,只是说看上去变成了两重循环
通过Judge Small后:
public class Solution { public ArrayList<ArrayList<Integer>> threeSum(int[] num) { int length = num.length; ArrayList<ArrayList<Integer>> results = new ArrayList<ArrayList<Integer>>(); ArrayList<Integer> list; for (int i = 0; i < length - 2; ++i) for (int j = i + 1; j < length - 1; ++j) for (int k = j + 1; k < length; ++k){ int sum = num[i] + num[j] + num[k]; if (sum == 0){ list = new ArrayList<Integer>(); list.add(num[i]); list.add(num[j]); list.add(num[k]); Collections.sort(list); if (!results.contains(list)) results.add(list); } } return results; } }
尝试O(N2)算法
public class Solution { public ArrayList<ArrayList<Integer>> threeSum(int[] num) { int length = num.length; ArrayList<ArrayList<Integer>> results = new ArrayList<ArrayList<Integer>>(); ArrayList<Integer> list; ArrayList<Integer> input = new ArrayList<Integer>(); for (int i = 0; i < length; ++i) input.add(num[i]); Collections.sort(input); HashMap<Integer, ArrayList<ArrayList<Integer>>> map = new HashMap<Integer, ArrayList<ArrayList<Integer>>>(); for (int i = 1; i < length - 1; ++i) for (int j = i + 1; j < length; ++j){ //ArrayList<ArrayList<Integer>> tempBucket = new ArrayList<ArrayList<Integer>>(); int sum = input.get(i) + input.get(j); ArrayList<Integer> tempBucket = new ArrayList<Integer>(); tempBucket.add(i); tempBucket.add(j); tempBucket.add(input.get(i)); tempBucket.add(input.get(j)); if (map.containsKey(sum)) map.get(sum).add(tempBucket); else{ ArrayList<ArrayList<Integer>> tempList = new ArrayList<ArrayList<Integer>>(); tempList.add(tempBucket); map.put(sum, tempList); } } for (int i = 0; i < length - 1; ++i) for (int sum: map.keySet()) if (input.get(i) + sum == 0){ ArrayList<ArrayList<Integer>> tempList = map.get(sum); for (ArrayList<Integer> li: tempList) if (li.get(0) > i){ list = new ArrayList<Integer>(); list.add(input.get(i)); list.add(li.get(2)); list.add(li.get(3)); if (!results.contains(list)) results.add(list); } } return results; } }
最后在stackoverflow上找到了答案 唉
http://stackoverflow.com/questions/10732522/difference-between-two-similar-algorithms-of-3sum
public ArrayList<ArrayList<Integer>> threeSum(int[] num) { Arrays.sort(num); HashSet<ArrayList<Integer>> lstSoln = new HashSet<ArrayList<Integer>>(); ArrayList<Integer> tempArr = null; for (int i = 0; i < num.length; i++) { int j = i + 1; int k = num.length - 1; while (j < k) { int sum3 = num[i] + num[j] + num[k]; if (sum3 < 0) { j++; } else if (sum3 > 0) { k--; } else { tempArr = new ArrayList<Integer>(); Collections.addAll(tempArr, num[i], num[j], num[k]); lstSoln.add(tempArr); j++; k--; } } } return new ArrayList<ArrayList<Integer>>(lstSoln); }
第二天想了一下,发现其实还是三重循环,k其实就是j里面的一层循环,只是说看上去变成了两重循环
发表评论
-
Insert Interval
2012-11-11 01:33 543各种条件真复杂,不仅是边界条件,而且还要分很多种情况讨论 而且 ... -
Implement strStr()
2012-11-07 15:44 584唉 终于到了要记算法的时候了 KMP。。。还没写完 回去再写。 ... -
Flatten Binary Tree to Linked List && Generate Parentheses && Gray Code
2012-11-07 00:08 1094Flatten太简单了 递归 一遍过 oh yeah = = ... -
First Missing Positive
2012-11-06 22:50 590唉 想了很久都没想出来 后来还是看了网上的答案 >_&l ... -
Edit Distance
2012-11-06 00:27 673动规 就是递推。。。比较难想 然后数组长度设置比字符串长度多一 ... -
Divide Two Integers
2012-11-05 00:12 714自己实现除法 太太太恶心了。。。。 就是用位移代替了乘法,然后 ... -
Distinct Subsequences
2012-11-04 21:44 659动规,从前到后用T的每一个字符i,扫描S的每一个字符j。维护一 ... -
Count and Say
2012-11-04 18:46 693public class Solution { ... -
Convert Sorted Array to Binary Search Tree && Convert Sorted List to Binary Sear
2012-11-04 17:36 827/** * Definition for binary ... -
Container With Most Water
2012-11-04 00:25 698本来以为是个简单的题目,直接二重循环,结果小测试过了,大测试超 ... -
Construct Binary Tree from Inorder and Postorder Traversal
2012-11-03 23:40 748不知道为什么错了。。。eclipse上明明是正确的啊 leet ... -
Combinations
2012-11-03 22:19 607全排列 按理说很简单,可是用递归写,边界条件就还是难想清楚,s ... -
Combination Sum I && II
2012-11-03 21:41 751还是递归 但是边界条件以及边界上的处理不容易搞清楚(一开始我就 ... -
climbing stairs
2012-11-03 17:18 611一开始觉得是简单的组合数学题,但是写完之后发现,首先组合数不是 ... -
Binary Tree Inorder Traversal
2012-11-02 23:51 615I简单 直接递归就好 addAll函数很好用 /** ... -
Best Time to Buy and Sell Stock I & II
2012-11-02 22:05 1045啊 第一次直接过small和big测试 好爽!虽然主要是以前知 ... -
Balanced Binary Tree
2012-11-01 23:38 610/** * Definition for binary ... -
Anagrams
2012-10-31 00:33 589这题实在是没懂它的意思。。。囧啊 import java. ... -
Add Two Numbers
2012-10-30 23:03 615这题不难 直接上递归就行 /** * Definiti ... -
Add Binary
2012-10-29 00:07 602public String addBinary(Strin ...
相关推荐
3sum-hard经典问题的描述与各种3sum-hard问题的综述
3sum.asm
双指针算法,python数组双指针算法求和问题LeetCode2sum3sum4sum含代码
文档python数组双指针算法求和问题LeetCode2sum3sum4sum含代码提取方式是百度网盘分享地址
python python_leetcode面试题解之三数之和_3sum
3sum problem and solution.
linux sm3sum工具 光盘sm3sum 使 ./sm3sum-帮助
3sum leetcode-练习 算法实践 15. 3和 给定一个由 n 个整数组成的数组 nums,nums 中是否有元素 a、b、c 使得 a + b + c = 0? 在数组中找到所有唯一的三元组,其总和为零。 示例输入: [-1, 0, 1, 2, -1, -4] 示例...
3sum 力码 力扣算法 (注:“ :locked: " 表示你需要来自 Leetcode) # 标题 解决方案 困难 001 简单的 002 中等的 003 中等的 004 难的 005 中等的 006 简单的 007 简单的 008 简单的 009 简单的 010 难的 011 中等...
3sum # Leetcode 解决方案以下是我在 Leetcode 上解决的一些问题,如果你喜欢/找到任何你的答案,请留下一个星。 如果你想与我联系,我在下面分享了我的 Linkedin URL。 问题 # 标题 # 解决方案 困难 1 二和 简单...
Keccak 代码包的哈希模式接口。 该程序说明了 Keccak 排列的使用。 该程序的唯一目的是演示和测试 KECCAK 排列。 版权所有 (c) 2012-2013 McDevitt Heavy Industries, Ltd. (MHI) 保留所有权利。
3sum leetcode-curation-topical 精选 Leetcode 问题,按主题/概念分类。 我的策展标准是问题必须是有价值的,而不仅仅是为了难而难。 有价值的问题通常可以以不同的时间/空间效率(通过使用各种数据结构)以多种...
js代码-15. 3Sum
js代码-16. 3Sum Closest
3-sum算法求解 python http://blog.csdn.net/qq575787460/article/details/39100531的配套资源
sum(2,3,4)和sum(2)(3)(4)输出值一样
18 3Sum Closest 57 19 String to Integer (atoi) 59 20 Merge Sorted Array 61 ... ... 231 Counting Bits 561 232 Maximum Product of Word Lengths 563 233 Gray Code 565 234 Permutations 567 235 Permutations...
15. 3Sum 16. 3Sum Closest 17. Letter Combinations of a Phone Number 18. 4Sum 19. Remove Nth Node From End of List 20. Valid Parentheses 21. Merge Two Sorted Lists 22. Generate Parentheses 23. Merge k ...