数据结构与算法-005-数组-三数之和

三数之和

• 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
• 注意：答案中不可以包含重复的三元组。
• 题目来自Leetcode

暴力解题

public List<List<Integer>> threeSum(int[] nums) {
        // 暴力法，三遍循环，O(n^3)，该方式在leetcode执行会超时
        // 要求：返回结果不重复
        // 先将数据进行一次排序，这样后面处理起来方便
        Arrays.sort(nums);
        Set<String> distinct=new HashSet<>();
        List<List<Integer>> data=new LinkedList<List<Integer>>();
        for(int i=0;i<nums.length;i++){
            for(int j=i+1;j<nums.length;j++){
                for(int n=j+1;n<nums.length;n++){
                    if((nums[i]+nums[j]+nums[n])==0){
                        List<Integer> temp=new LinkedList<Integer>();
                        temp.add(nums[i]);
                        temp.add(nums[j]);
                        temp.add(nums[n]);
                        // 排序是为了方便对数据进行hash，这样就能去重了
                        // 后排序模式，结果也正确，但是无法通过leetcode测试，因为leetcode 结果是有序的
                        // Collections.sort(temp);
                        String tt=temp.toString();
                        if(distinct.add(tt)){
                            data.add(temp);
                        }
                    }
                }
            }
        }
        return data;
    }

双指针法，参考

     public List<List<Integer>> threeSum(int[] nums) {
        // 使用快慢指针法(双指针法)
        // 时间复杂度降低为O(n)+O(nlogn)
        List<List<Integer>> data=new LinkedList<>();
        // 边界条件处理,小于3个元素，则直接返回
        if(nums.length<3){
            return data;
        }
        // 等于3个元素，直接判断
        if(nums.length==3){
            if((nums[0]+nums[1]+nums[2])==0){
                List<Integer> temp=new LinkedList<>();
                temp.add(nums[0]);
                temp.add(nums[1]);
                temp.add(nums[2]);
                // leetcode 判题需要，所以排下序 ╮(╯▽╰)╭ 
                Collections.sort(temp);
                data.add(temp);
                return data;
            }
        }

        // 数据做一次排序，方便后续处理,主要是方便去重
        Arrays.sort(nums);
        for(int i=0;i<nums.length;i++){
            // 因为已经排序过了，所以当遇上大于0的数字时，后面的数字加起来是不会等于0的，所以直接返回结果即可
            if(nums[i]>0){
                return data;
            }
            // 跳过相同元素
            if(i>0 && nums[i]==nums[i-1])
                continue;

            int left=i+1,right=nums.length-1;
            while(left<right){
                int ret=nums[i]+nums[left]+nums[right];
                if(ret==0){
                    List<Integer> temp=new LinkedList<>();
                    temp.add(nums[i]);
                    temp.add(nums[left]);
                    temp.add(nums[right]);
                    data.add(temp);
                    // 去重
                    while(left<right&&nums[left]==nums[left+1]){
                        left++;
                    }
                    // 去重
                    while(left<right&&nums[right]==nums[right-1]){
                        right--;
                    }
                    // 左右移动一位到相同元素的最后一个
                    left++;
                    right--;
                }else if(ret>0){
                    // 和大于0，说明右面元素值过大，右指针移动
                    right--;
                }else{
                    // 和小于0,说明左边元素值过小，左指针移动
                    left++;
                }
            }
        }
        return data;
    }