[LeetCodeNote][java][双指针]15.三数之和

15. 三数之和 - 力扣（LeetCode） (leetcode-cn.com)

题目描述：

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

示例2：

输入：nums = []
输出：[]

示例3：

输入：nums = [0]
输出：[]

老规矩先上代码！

class Solution {
    public List> threeSum(int[] nums) {
        Arrays.sort(nums);
        
        List> ans = new ArrayList>(); 
        for(int i=0;i){
            if(i>0&&(nums[i]==nums[i-1])){
                continue;
            }
            int c=nums.length-1;
            int target = -nums[i];
            for(int j=i+1;j){
                if(j>i+1&&(nums[j]==nums[j-1])){
                    continue;
                }
                while(c>j&&(nums[c]+nums[j])>target){
                    --c;
                }
                if(c==j) break;
                if(nums[c]+nums[j]==target){
                    List l = new ArrayList();
                    l.add(nums[i]);
                    l.add(nums[j]);
                    l.add(nums[c]);
                    ans.add(l);
                }
            }
        }
        return ans;
    }
}

虽说毫无关系，但是回忆一下两数之和：给定一个和返回两个数组下标

当时用的方法是java中HashMap的几个函数实现的

然后说下这道题

如果也使用HashMap 要算满两层循环（突然意识到也是两层循环哎！一会儿就去写写试试

对于数组问题 先想排序！

这题使用双指针巧妙避免了三重循环

拿示例1的输入举例：

所谓的双指针其实是j和c

j从i+1开始往后走，始终比c小，c从nums.length-1开始往前走，始终比j大

每一个i确定了一个target值为0-nums[i]，也就是要找一对nums[j]和nums[c]的和为nums[i]的负数使三个数和为零。

需要注意的点：

由于题目要求答案中不可以包含重复的三元组，

所以例如如果i指向了-1位置……emmm这个例子不太好说明我们假设两个-1中间再加一个-1奥

如果i指向了第一个-1 它找到了一组-1 -1 2

等到下一轮循环i指向了第二个-1 它又找到了一组-1 -1 2 

显然就重复了

所以我们规定，i如果相同，不重复找。

j同理。

c不能等于j和超过j

——————————————————手动分界线————————————————————

坚持刷题的第五天了

感觉写代码确实是顺了一些，看题解也看得快了

虽然做的题都很基础 但是小菜鸡就一步一步来吧

加油加油

（做题笔记做的属实是很草率，希望能有一些改进

（以后多用平板画图试试