[Vssue]0015.三数之和.md

[youngyangyang04]

https://programmercarl.com/0015.%E4%B8%89%E6%95%B0%E4%B9%8B%E5%92%8C.html

[fengbaobao]

双指针真是妙~

[Du1in9]

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {
            int a = nums[i];
            if (a > 0) break;
            if (i > 0 && a == nums[i - 1]) 
                continue;               // a 去重
            int left = i + 1;
            int right = nums.length - 1;
            while (right > left) {
                int b = nums[left];
                int c = nums[right];
                if (a + b + c > 0) {
                    right--;
                } else if (a + b + c < 0) {
                    left++;
                } else {
                    List<Integer> res = Arrays.asList(a, b, c);
                    result.add(res);

                    while (right > left && b == nums[left + 1]) 
                        left++;         // b 去重
                    while (right > left && c == nums[right - 1]) 
                        right--;        // c 去重      
                    right--;
                    left++;
                }
            }
        }
        return result;
    }
}

[bupatianhei666]

两数之和我也用了双指针

    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList<ArrayList<Integer>>();
        HashMap<Integer, ArrayList<ArrayList<Integer>>> map = new HashMap<>();

        //统计两两相加的元组结果
        for(int i = 0;i < nums.length; i++) {
            for(int j = i + 1; j < nums.length; j++) {
                int k = nums[i] + nums[j];
                ArrayList<ArrayList<Integer>> l = map.getOrDefault(k, new ArrayList<ArrayList<Integer>>());
                ArrayList<Integer> al = new ArrayList<>(){nums[i], nums[j]};
                l.add(al);
                map.push(k, l);
            }
        }

        for(int i = 0;i < nums.length; i++) {
            int k = -nums[i];
            ArrayList<ArrayList<Integer>> l = map.getOrDefault(k, null);
            if(l == null) {
                continue;
            }

            //如果存在，则取出加入ans，并在map中把其删除
            for(int i = 0;i < l.size(); i++) {
                ArrayList<Integer> a = l.get(i);
                a.add()
            }
        }
    }
}```

[mockyd]

不懂java的方法二，也就是使用哈希集合的方法。对b的去重为什么要判断 j-2 这个元素？只跟 j-1 对比不就可以了吗？

[mockyd]

@mockyd

不懂java的方法二，也就是使用哈希集合的方法。对b的去重为什么要判断 j-2 这个元素？只跟 j-1 对比不就可以了吗？

我了解了，因为如果只跟 j-1 对比，会导致跳过(-2,1,1)这种情况。 也就是三元组的第二个和第三个元素是可能相同的，所以在做去重的时候，不能按照j、j-1、j-2相等来看，而应该是按照(j, j-1)和(j-1,j-2)相等来理解

[YuGuilliman]

不是很懂这里，我觉得right右移和left右移动效果一样的，在可以动的情况下“如果 nums[i] + nums[left] + nums[right] < 0 说明 此时 三数之和小了，left 就向右移动，才能让三数之和大一些，直到left与right相遇为止。”

[YuGuilliman]

@YuGuilliman

解释一下在不越界的情况下为什么单独调整left+=1而不用right+=1: 因为一开始left和right就是位于边界，如果出现了right下调的情况使得right+=1是可以被操作的; 再执行right+=1相当于回溯到之前讨论过的不成立的情况，所以不需要right+=1，只有left+=1;

[Bryan-CR7]

打卡：双指针法一定要排序

[numbnumb2]

请问 这里 第一个 hash解法 中对于“元素b”的去重是否出现了错误？

如果元素排序为 [-1,-1,-1,-1,0,0,0,0,1,1,1,1] ，那么此判断条件应该会在set中放入两个-1值和两个0值，同时使用两个1值进行result的输出，那么应该会出现重复结果。

如果改为 if ( j > i+1 && nums[ j ] == nums[ j - 1 ]) return ; 是否会更为妥当？ 此种写法又有哪些欠考虑的地方呢？

[mishiroo]

感觉没啥能优化的空间了，卡在308/313过不去了，大力出奇迹失败哩xdm

#
# @lc app=leetcode.cn id=15 lang=python3
#
# [15] 三数之和
#
from typing import List
# @lc code=start
# 把三元组看成三个独立数组的问题（类似四数之和）
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        hashmap = {}
        res = []
        # 不考虑重复 直接统计符合要求的数组（并统计索引便于去重）
        l = len(nums)
        for i in range(l):
            for j in range(i,l):
                if i != j:
                    if hashmap.get(nums[i] + nums[j]) != None:
                        hashmap[nums[i] + nums[j]].append([i, j, 0]) 
                    else:
                        hashmap[nums[i] + nums[j]] = [[i, j, 0]]

        # 分析是否可能组成
        for k in range(l):
            if hashmap.get(-nums[k]):  # 如果可以凑出三元组
                for h in hashmap[-nums[k]]:
                    h[2] = k
                    if h[1] != h[2] and h[0] != h[2]:
                        b = sorted([nums[h[0]], nums[h[1]], nums[h[2]]])
                        if b in res:
                            pass
                        else:
                            res.append(b)

        return res            
# @lc code=end

[naku111]

@YuGuilliman

不是很懂这里，我觉得right右移和left右移动效果一样的，在可以动的情况下“如果 nums[i] + nums[left] + nums[right] < 0 说明 此时 三数之和小了，left 就向右移动，才能让三数之和大一些，直到left与right相遇为止。”

right每次取的是数组右边界，right只能--，++就越界了