15. 三数之和（中等 数组 双指针 排序）

15. 三数之和

给你一个包含 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]
输出：[]

提示：

0 <= nums.length <= 3000
-105 <= nums[i] <= 105

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

分析&题解

分析

这道题用哈希表判断重复太复杂，使用双指针稍微简单点，主要是降低时间复杂度，减少每个相同数的遍历，同时使用双指针避免重复遍历。

题解（Java）

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        //先从小到大排序
        Arrays.sort(nums);
        int n = nums.length;
        if (nums == null || n <= 2) {
            return ans;
        }
        //枚举第一个数，末尾是第n - 2个数
        for (int first = 0; first < n - 2; first++) {
        	//第一个数不能与之前的重复
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }
            //因为排过序，所以第一个数大于0后续就不用再判断了
            if (nums[first] > 0) {
                break;
            }
            //第三个数从后往前遍历，减少遍历重复
            int third = n - 1;
            //枚举第一个数，末尾是第n - 1个数
            for (int second = first + 1; second < n - 1; second++) {
            	//第二个数不能与之前的重复
                if (second > first + 1 && nums[second] == nums[second - 1]) {
                    continue;
                }
                //循环找到能使和为0的third
                while (nums[first] + nums[second] + nums[third] > 0 && third > second) {
                    third--;
                }
                //second与third相等就是没找到，进行下一个second的判断
                if (second == third) {
                    break;
                }
                //找到了用新建的List集合存起来再添加到答案中
                if (nums[first] + nums[second] + nums[third] == 0) {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[first]);
                    list.add(nums[second]);
                    list.add(nums[third]);
                    ans.add(list);
                }
            }
        }
        return ans;
    }
}

最后

以上就是矮小溪流为你收集整理的15. 三数之和（中等 数组 双指针 排序）的全部内容，希望文章能够帮你解决15. 三数之和（中等 数组 双指针 排序）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。