Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:
Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
The solution set must not contain duplicate triplets.
For example, given array S = {-1 0 1 2 -1 -4},
A solution set is:
(-1, 0, 1)
(-1, -1, 2)
这道题目脑子没转过来,一直想要用贪心的方式做,然后各种bug,后来转变过来,可以根据target来选择。还有一种是可以用暴力方式做,这种方法一个很烦的地方就是去除重复的子项。自己试过好多中方式,然后发现自己对hashCode方法没有理解彻底,特别在重写的hashcode方法不知道。
这个是在AbstractList这个类中重写的方法。所以我们可以用HashSet来排除多余项。具体代码都是网上copy下来的,另一种方法的详细解释在这里这里
暴力方法代码
另外的方式
Note:
Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
The solution set must not contain duplicate triplets.
For example, given array S = {-1 0 1 2 -1 -4},
A solution set is:
(-1, 0, 1)
(-1, -1, 2)
这道题目脑子没转过来,一直想要用贪心的方式做,然后各种bug,后来转变过来,可以根据target来选择。还有一种是可以用暴力方式做,这种方法一个很烦的地方就是去除重复的子项。自己试过好多中方式,然后发现自己对hashCode方法没有理解彻底,特别在重写的hashcode方法不知道。
public int hashCode() { int hashCode = 1; for (E e : this) hashCode = 31*hashCode + (e==null ? 0 : e.hashCode()); return hashCode; }
这个是在AbstractList这个类中重写的方法。所以我们可以用HashSet来排除多余项。具体代码都是网上copy下来的,另一种方法的详细解释在这里这里
暴力方法代码
public List<List<Integer>> threeSum(int[] num) { HashSet rs = new HashSet(); int len = num.length; Arrays.sort(num); if(len <= 2) return new ArrayList(rs); for(int i = 0; i < len-2; i++) { if(num[i] > 0) break; for(int k = len-1; k > i+1; k--) { if(num[k] < 0) break; int ab = num[i] + num[k]; int c = -ab; int j = bs(c, num, i+1, k-1); if(j>0) { ArrayList elem = new ArrayList(); elem.add(num[i]); elem.add(num[j]); elem.add(num[k]); elem.hashCode(); rs.add(elem); } } } return new ArrayList(rs); } int bs(int c, int[] num, int l, int r) { if(num[l] > c || num[r] < c) return -1; while(l <= r) { int m = (l+r)/2; if(num[m] == c) return m; else if(num[m] < c) l = m+1; else r = m-1; } return -1; }
另外的方式
public ArrayList<ArrayList<Integer>> threeSum(int[] num) { ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>(); if (num == null || num.length < 3) return result; int n = num.length; Arrays.sort(num); for (int i = 0; i < n; i++) { int target = -num[i]; int p = i + 1, q = n - 1; while (p < q) { if (num[p] + num[q] < target) p++; else if (num[p] + num[q] > target) q--; else { ArrayList<Integer> tmp = new ArrayList<Integer>(); tmp.add(-target); tmp.add(num[p]); tmp.add(num[q]); result.add(tmp); p++; q--; // remove duplicates while (p < n && num[p] == num[p - 1]) p++; while (q >= i + 1 && num[q] == num[q + 1]) q--; } } // remove duplicates while (i < n - 1 && num[i + 1] == num[i]) i++; } return result; }
发表评论
-
Merge k Sorted Lists
2015-03-12 19:55 326Merge k sorted linked lists and ... -
Generate Parentheses
2015-03-12 19:50 365Given n pairs of parentheses, w ... -
Generate Parentheses
2015-03-05 22:39 0Given n pairs of parentheses, w ... -
Valid Parentheses
2015-03-05 22:33 308Given a string containing just ... -
Remove Nth Node From End of List
2015-03-05 22:31 340Given a linked list, remove the ... -
Letter Combinations of a Phone Number
2015-03-05 22:30 331Letter Combinations of a Phone ... -
4Sum
2015-03-05 22:26 312Given an array S of n integers, ... -
3Sum Closest
2015-03-05 22:25 292Given an array S of n integers, ... -
Longest Common Prefix
2015-03-03 22:21 328Write a function to find the lo ... -
Roman to Integer
2015-03-03 22:20 327Given a roman numeral, convert ... -
Integer to Roman
2015-03-01 23:35 289Given an integer, convert it to ... -
Container With Most Water
2015-03-01 22:55 323Given n non-negative integers a ... -
Regular Expression Matching
2015-03-01 20:19 367Implement regular expression ma ... -
Palindrome Number
2015-02-13 22:08 331Determine whether an integer is ... -
String to Integer (atoi)
2015-02-13 11:07 343Implement atoi to convert a str ... -
Reverse Integer
2015-02-12 23:39 227Reverse digits of an integer. ... -
ZigZag Conversion
2015-02-12 23:37 255The string "PAYPALISHIRING ... -
Longest Palindromic Substring
2015-02-12 22:50 334Given a string S, find the long ... -
Add Two Numbers
2015-02-12 22:12 300You are given two linked lists ... -
Longest Substring Without Repeating Characters
2015-02-11 21:14 425[size=24px;]Longest Substring W ...
相关推荐
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 ...