15. 三数之和--🀄️


15. 三数之和

难度中等 3030
给你一个包含 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]
输出:[]

    public List<List<Integer>> threeSum(int[] nums) &#123;
        int n = nums.length;
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        // 枚举 a
        for (int first = 0; first < n; ++first) &#123;
            // 需要和上一次枚举的数不相同
            if (first > 0 && nums[first] == nums[first - 1]) &#123;
                continue;
            &#125;
            // c 对应的指针初始指向数组的最右端
            int third = n - 1;
            int target = -nums[first];
            // 枚举 b
            for (int second = first + 1; second < n; ++second) &#123;
                // 需要和上一次枚举的数不相同
                if (second > first + 1 && nums[second] == nums[second - 1]) &#123;
                    continue;
                &#125;
                // 需要保证 b 的指针在 c 的指针的左侧
                while (second < third && nums[second] + nums[third] > target) &#123;
                    --third;
                &#125;
                // 如果指针重合,随着 b 后续的增加
                // 就不会有满足 a+b+c=0 并且 b<c 的 c 了,可以退出循环
                if (second == third) &#123;
                    break;
                &#125;
                if (nums[second] + nums[third] == target) &#123;
                    List<Integer> list = new ArrayList<Integer>();
                    list.add(nums[first]);
                    list.add(nums[second]);
                    list.add(nums[third]);
                    ans.add(list);
                &#125;
            &#125;
        &#125;
        return ans;
    &#125;

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/3sum/solution/san-shu-zhi-he-by-leetcode-solution/

没太懂边界问题

    ///至少一个正数一个负数
    public List<List<Integer>> threeSum(int[] nums) &#123;
        int n = nums.length;
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        // 枚举 a
        for (int first = 0; first < n; ++first) &#123;
            // 需要和上一次枚举的数不相同
            if (first > 0 && nums[first] == nums[first - 1]) &#123;
                continue;
            &#125;
            // c 对应的指针初始指向数组的最右端
            int third = n - 1;
            int target = -nums[first];
            // 枚举 b
            for (int second = first + 1; second < n; ++second) &#123;
                // 需要和上一次枚举的数不相同
                if (second > first + 1 && nums[second] == nums[second - 1]) &#123;/// >=
                    continue;
                &#125;
                // 需要保证 b 的指针在 c 的指针的左侧
                while (second < third && nums[second] + nums[third] > target) &#123;/// <=
                    --third;
                &#125;
                // 如果指针重合,随着 b 后续的增加
                // 就不会有满足 a+b+c=0 并且 b<c 的 c 了,可以退出循环
                if (second == third) &#123; /// >
                    break;
                &#125;
                if (nums[second] + nums[third] == target) &#123;
                    List<Integer> list = new ArrayList<Integer>();
                    list.add(nums[first]);
                    list.add(nums[second]);
                    list.add(nums[third]);
                    ans.add(list);
                &#125;
            &#125;
        &#125;
        return ans;
    &#125;

文章作者:   future
版权声明:   本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 future !
 上一篇
面试题 02.01. 移除重复节点 面试题 02.01. 移除重复节点
面试题 02.01. 移除重复节点难度简单 90编写代码,移除未排序链表中的重复节点。保留最开始出现的节点。示例 1:** 输入:[1, 2, 3, 3, 2, 1]** 输出:[1, 2, 3] 示例 2:** 输入:[1, 1, 1,
下一篇 
剑指 Offer 53 - II. 0~n-1中缺失的数字 剑指 Offer 53 - II. 0~n-1中缺失的数字
剑指 Offer 53 - II. 0 ~ n-1 中缺失的数字难度简单 110一个长度为 n-1 的递增排序数组中的所有数字都是唯一的,并且每个数字都在范围 0 ~ n-1 之内。在范围 0 ~ n-1 内的 n 个数字中有且只有一个数字
  目录