哈希表-三数之和

代码随想录-刷题笔记

15. 三数之和 - 力扣（LeetCode）

内容：

这道题讲真真挺有意思的。双指针的用法很巧妙，而且去重的细节多到离谱。

哈希表本身的做法我没搞懂，而且确实复杂的很。既然有更好的方法就一步到位

本身思路也比较好想，但是中间超级多的细节。可能是我做的感觉最琐碎的一道题了 。

三者之和等于零，不妨令三者为 nums[i] , nums[j] , nums[k]

nums[i] + nums[j] = -nums[k] 这里的 三个数值不进行大小区分

 实际上，确定两个就最OK了。

最后要得到的结果也是一个不重复的三元组，由此，需要得到三个具体的数就好了。

不需要记录下标 ,这点很重要(我最开始的思路搞错过)

无非就是几种结果

Part1. 负+正+正

Part2. 0+0+0

Part3. 负+负+正

因此，对于一个无规律的数组，想要找到正负的一个相对性，最好的办法是先进行排序

排完序还有好处，可以看到这个值和0进行比较是更大还是更小

 定1 ， 走2

遍历一个i , 然后 用left和right去缩范围.

复杂度O(n^2)无法避免的.

有两种情况,这两种情况讨论好了之后都很简单

nums[i]+nums[right]+nums[left] > 0 -> right-1

nums[i]+nums[right]+nums[left] < 0 -> left+1

代码如下:

去重的关键逻辑在代码注释里面,可以仔细看一下

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        for(int i = 0 ; i < nums.length ; i++) {
            if(nums[i] > 0) break; 
            //最小的都大于零
            if(i>0 && nums[i-1] == nums[i]) continue;
            //这一步很关键,去重,如果是nums[i]==nums[i+1] 是防止 元组内重复
            int left = i + 1;
            int right = nums.length-1;
            while (right>left) {
                if(nums[i]+nums[right]+nums[left] > 0) {
                    right--;
                    //while(right> left && nums[right] == nums[right+1]) right--;
                }else if(nums[i]+nums[right]+nums[left] < 0) {
                    left++;
                    //while (right>left && nums[left] == nums[left-1]) left++;
                }else{
                    result.add(new ArrayList<>(Arrays.asList(nums[i],nums[left],nums[right])));
                    while (right > left && nums[left] == nums[left+1]) {
                        left++;
                    }//去重 , 这里能跟后一位比较的原因是因为该位已经进入元组内
                    while (right>left && nums[right] == nums[right-1]) {
                        right--;
                    }
                    left++;
                    right--;
                }
            }

        }
        return result;
    }
}

总结：

该题最重要的就是进行去重，还有就是双指针的巧用~

注意减枝！！还有就是比较的顺序。进行去重！

元组内还是不同元组之间的比较