2018-10-28这个是不是没有考虑“不重复的”三元组这个条件？ 1 17
2018-10-28老师，可以提供一下java语言的第一种解法吗…😂一直没法去重 2 13
2019-01-12第二种解法用set无法解决,这里用map来替代,不过性能真的很一般
public List<List<Integer>> threeSum(int[] nums) {
if(nums ==null || nums.length == 0){
return new ArrayList();
}
List<List<Integer>> resultList = new ArrayList();
//要先对数组进行排序
Arrays.sort(nums);
for(int i=0;i<nums.length-1;i++){
//重复的过滤掉
if(i>0 && nums[i] == nums[i-1])
continue;
Map<Integer,Integer> targetMap = new HashMap<>();
for(int j=i+1;j<nums.length;j++){
if(targetMap.containsKey(nums[j])){
if(targetMap.get(nums[j]) == 0){
resultList.add(Arrays.asList(nums[i],nums[j],-nums[i] - nums[j]));
targetMap.put(nums[j],1);
}
}else{
targetMap.put(-nums[i] - nums[j],0);
}
}
}
return resultList;
}展开 5
2018-10-27关于第二种解法...
由于给出的数组不排除重复数,比如-1,-1,2这种..
按照你前面小白板的说法是直接将数组扔到set去判断...
但这种情况在假设我们只有-1,2而木有第三个-1这个数时也是可以得出{-1,-1,2}这个解的..
ps你后面py代码我没太看懂,,,展开作者回复: 这是代码实现的一个细节问题：在遍历的时候，需要把当前遍历元素从set里去掉；每次遍历完一个元素再将其加回到set中。
4- 2018-11-01第一种解法没看明白。。自己拓展2sum的写了3sum和4sum，感觉hashset/map解法很麻烦，而且用python写很容易超时。
貌似这类N-sum问题的解法还是双指针比较好啊，leetcode讨论区有一个双指针通解的，N>=2以上采用递归降阶，速度很快推荐大家都去看看。 3 - 2019-07-28java实现，供参考；Arrays.sort在jdk里使用了归并排序、快速排序、插入排序的组合策略（根据元素的多寡来设置的门限），会在循环外层浪费一定时间，但不影响大O的复杂度；提交力扣会有概率性地被判定为超时的情况，比如输入nums为{0, 0, 0}的时候也会做几次空跑的循环，应该还有优化的空间。
public List<List<Integer>> threeSum(int[] nums) {
Set<List<Integer>> result = new HashSet<>();
//排序需要（Arrays.asList对基本类型的数组int[]无法准确转化为期望的list）
List<Integer> copy = new ArrayList<Integer>() {{
for (int num : nums) this.add(num);
}};
copy.sort(Comparator.comparing(Integer::intValue));
Set<Integer> cSet;//预期的c值
loop1:
for (int i = 0; i < copy.size(); i++) {
int a = copy.get(i);
//加速（与上一个值相等，则上一轮已经找到过相同解法）
if (i > 0 && a == copy.get(i - 1)) continue loop1;
cSet = new HashSet<>();
loop2:
for (int j = i + 1; j < copy.size(); j++) {
int b = copy.get(j);
if (!cSet.contains(b)) {
cSet.add(-(a + b));//记录本轮的解法预期的c值，c值在后续的loop2循环中命中时说明此解存在
} else {
//因为copy是有序的，a, -(a + b), b也将呈有序排列（此轮的b就是上轮的c值），所以可以用set来进行结果去重
result.add(Arrays.asList(a, -(a + b), b));
}
}
}
return new ArrayList<>(result);
}展开 2 
2018-12-25这个三元组的去重有点难，我是将三元组排序后将整个三元组放到Set中去重的。 2
2018-12-14这个题有一个非常难理解的地方需要一个小学的数学知识来理解一下:
a+b+c=0;
a=-b-c
b=-a-c
c=-a-b 1 2
2018-11-08问下老师，为什么最后一个解法 append((a,b,c))（返回三元组） 而不是 append([a,b,c]) （返回一个list） 2
2018-11-06第三种方法，快排也有时间复杂度，没算进去啊。。。作者回复: 快排 nlogn，小于 n×n ，另外也不是嵌套运算，所以只要算 n×n
1 2
2018-10-273sum是否可以一层遍历后，然后调用之前的2sum，是否实现更简单?复杂度也是N平方作者回复: 可以的。注意元素盼重的问题。
2
2019-10-08不能用set吧，这样可能出现2，2，4这种作者回复: 代码里需要进行判重的技术处理。
1
2019-10-06第一种写法没去重，稍作修改为以下代码：
```python
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
if len(nums) < 3: return []
r = []
nums.sort()
print(nums)
for i, v1 in enumerate(nums[:-2]):
if i >= 1 and nums[i-1] == v1: continue
d = {}
for v2 in nums[i+1:]:
if v2 not in d:
d[-v1-v2] = 0
elif d[v2] == 0:
r.append([v1, -v1-v2, v2])
d[v2] += 1
return r
```展开 1
2019-02-11第一种办法在leetcode上没有通过测试啊 1 1
2019-01-07谢谢老师， 解决了我一直以来的困惑。
这道题我在leetcode上面提交了10次， 最后一次通过是用了最后一种办法， 即left和right不断逼近的方法。 其余的办法一律是： 超出时间限制（使用JS实现）。
我想破脑袋就是无法解决， 结果一看视频试了试， 就成功了。那种感觉真爽。作者回复: 👍🏻👍🏻👍🏻
1- 2018-10-28以来2sum的3sum实现，已经在leetcode上通过。
class Solution(object):
def threeSum(self, nums):
nums.sort()
res = []
for i, num in enumerate(nums):
if i > 0 and nums[i] == nums[i-1]:
continue
new_nums = nums[i+1:]
two_sums = self.twoSum(new_nums, -num)
for two_sum in two_sums:
res.append([num, new_nums[two_sum[0]], new_nums[two_sum[1]]])
return res
def twoSum(self, nums, target):
d = {}
res = []
hit = False
for i, num in enumerate(nums):
if i > 1 and nums[i] == nums[i-1] and hit:
continue
if num in d:
res.append([d[num], i])
hit = True
else:
d[target - num] = i
hit = False
return res展开 1 
2020-02-09public class Test3Sum2 {
static int arr[] = new int[]{-1, 100, 222, -44, 2, -1};
static int target = 0;
public static void main(String[] args) {
Test3Sum2 test3Sum = new Test3Sum2();
int arr[] = test3Sum.sum3();
System.out.println(arr[0] + "," + arr[1] + "," + arr[2]);
}
public int[] sum3() {
Map<Integer, Integer> cacheMap = Maps.newHashMap();
Set<Integer> sets = Sets.newHashSet();
for (int x = 0; x < arr.length - 1; x++) {
cacheMap.put(arr[x], x);
sets.add(x);
for (int y = x + 1; y < arr.length; y++) {
int find = target - arr[x] - arr[y];
if (cacheMap.containsKey(find)) {
int z = cacheMap.get(find);
if (z != x && z != y) {
return new int[]{x, y, cacheMap.get(find)};
} else {
cacheMap.put(arr[y], y);
sets.add(y);
}
} else {
cacheMap.put(arr[y], y);
sets.add(y);
}
}
}
return null;
}
}展开
2020-01-29没人发现这边讲的前后矛盾吗，第二种解法，直接将数据放到set里面，我看有人提出这个疑问，老师的回复是”在遍历的时候，需要把当前遍历元素从set里去掉；每次遍历完一个元素再将其加回到set中。“，这个说法本身就有问题吧，如果原生数据里面有两个相同的数，放到set里面去重只剩一个，那么当遍历到这个数时又把set里面的那个数去掉，set里面就没有这个数了，那么比如像[-1,-1,2]三元组就永远得不到。白板的时候老师认为第二种方法比第三种方法要好，因为第三种方法要排序会改变数据顺序，结果代码演示的时候，使用set的第二个方法，一上来就是先排序说是为了去重方便，这不前后矛盾吗？
2020-01-18set不能放重复元素啊
2020-01-12用set去重应该办不到 0 0 0 的case没法通过，用map可以处理，不过超时，放出来大家看下:
public List<List<Integer>> threeSum(int[] nums) {
if (nums == null || nums.length < 3) {
return Collections.emptyList();
}
Map<Integer, Integer> map = new HashMap<>();
for (int i : nums) {
put(map,i);
}
Set<List<Integer>> tmpRes = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
remove(map,nums[i]);
remove(map,nums[j]);
int third = -nums[i] - nums[j];
if(map.get(third) != null) {
List<Integer> tmp =Arrays.asList(nums[i], nums[j], third);
Collections.sort(tmp);
tmpRes.add(tmp);
}
put(map,nums[i]);
put(map,nums[j]);
}
}
return new ArrayList<>(tmpRes);
}
private void put(Map<Integer, Integer> map, Integer key) {
Integer val = map.get(key);
map.put(key, val == null ? 1 : ++val);
}
private void remove(Map<Integer, Integer> map, Integer key) {
Integer val = map.get(key);
map.put(key, val == 1 ? null : --val);
}展开