【剑指 Offer II】7 数组中和为 0 的三个数

题目

• 链接【剑指Offer II】007 数组中和为 0 的三个数
• 描述

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

总结：

1. 三个数字；
2. 和为 0；
3. 得到的结果集合不重复。

• 输入与输出

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

思路

刚开始的思路就 dfs + 回溯 + 剪枝，但是超时了。
有点魔怔了，组合问题都想着什么 dfs bfs。

正确的思路

1. 排序；
2. 遍历得到第一个数；
3. 二分查找第二、三个数；
4. 核心是去重。

代码

• dfs + 剪枝

class Solution {

    // 定义结果
    List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> threeSum(int[] nums) {
        // 不满足三个数就直接返回空结果集
        if (nums == null || nums.length == 0 || nums.length == 1) {
            return res;
        }

        // 排序, 方便剪枝
        Arrays.sort(nums);
        List<Integer> list = new ArrayList<>();
        dfs(nums,0,list,0);

        return res;
    }

    
    public void dfs(int[] nums, int index, List<Integer> list, int sum) {

        if (list.size() == 3 && sum == 0) {
            res.add(new ArrayList<>(list));
            return;
        }
        for (int i = index; i < nums.length; i++) {
            // 根据题意结果集最大为 3, 超过 3 个后 return 进行回溯
            if (list.size() > 3) return;

            // 剪枝
            if (i > index && nums[i] == nums[i-1]) {
                continue;
            }
            list.add(nums[i]);
            dfs(nums,i+1,list,sum+nums[i]);
            list.remove(list.size()-1);
        }
    }
}

• 正确解法

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        // 定义结果
        List<List<Integer>> res = new ArrayList<>();

        // 判断特殊情况
        if (nums == null || nums.length < 3) {
            return res;
        }

        // 排序  方便二分查找
        Arrays.sort(nums);

        // 查找
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            
            // i == 0 的话 nums[i-1] 数组越界 
            // 去重
            if (i != 0 && nums[i] == nums[i-1]) {
                continue;
            }

            // 二分查找
            int left = i+1;
            int right = len-1;
            while (left < right) {
                if (nums[left] + nums[right] + nums[i] == 0) {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[left]);
                    list.add(nums[right]);
                    list.add(nums[i]);
                    res.add(list);

                    // 去重
                    int tmp = nums[left];
                    while (left < right && tmp == nums[left]) {
                        left++;
                    }
                    tmp = nums[right];
                    while (left < right && tmp == nums[right]) {
                        right--;
                    }
                }else if (nums[left] + nums[right] + nums[i] > 0) {
                    right--;
                }else {
                    left++;
                }
            }
        }

        // 返回结果
        return res;
    }
}

最后

以上就是凶狠硬币为你收集整理的【剑指 Offer II】7 数组中和为 0 的三个数的全部内容，希望文章能够帮你解决【剑指 Offer II】7 数组中和为 0 的三个数所遇到的程序开发问题。

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