关于java:LeetCode015三数之和

三数之和

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

留神：答案中不能够蕴含反复的三元组。

示例阐明请见 LeetCode 官网。

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl…
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

解法一：暴力破解法

首先将数组 nums 排序，而后通过三重遍历，获取符合条件三元组，两头须要把反复的通过判断过滤掉。

解法二：双指针法

形容首先也是将 nums 排序，而后第一层遍历和第一种办法一样，获取第一个数字的索引 first，而后第二个数字索引second 和第三个数字索引 third 别离从 first 之后的数组中，从左至右获取符合条件的数字，直到 second 不小于 third 为止。

第二种办法比第一种办法少一层循环，所以效率高得多。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
    /**
     * 办法一：暴力破解法
     *
     * @param nums
     * @return
     */
    public static List<List<Integer>> threeSum(int[] nums) {if (nums == null || nums.length < 3) {return new ArrayList<>();
        }
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        int count = 0;
        // 第一层循环：遍历第一个数字
        for (int first = 0; first < nums.length - 2; first++) {if (nums[first] > 0) {return result;}
            // 不容许反复
            if (count > 0 && nums[first] == result.get(count - 1).get(0)) {continue;}
            // 第二重循环：遍历第二个数字
            for (int second = first + 1; second < nums.length - 1; second++) {
                // 以后 2 个数字之和曾经大于 0 了，遍历第三个数字曾经没有意义了
                if (nums[first] + nums[second] > 0) {break;}
                // 第三重循环：遍历第三个数字
                for (int three = second + 1; three < nums.length; three++) {if (nums[first] + nums[second] + nums[three] == 0) {if (count > 0 && nums[first] == result.get(count - 1).get(0) &&
                                nums[second] == result.get(count - 1).get(1) &&
                                nums[three] == result.get(count - 1).get(2)) {continue;}
                        ArrayList<Integer> temp = new ArrayList<>();
                        temp.add(nums[first]);
                        temp.add(nums[second]);
                        temp.add(nums[three]);
                        result.add(temp);
                        count++;
                        break;
                    }
                }
            }
        }
        return result;
    }

    /**
     * 办法二：双指针法
     *
     * @param nums
     * @return
     */
    public static List<List<Integer>> threeSum1(int[] nums) {if (nums == null || nums.length < 3) {return new ArrayList<>();
        }
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        // 第一层循环：遍历第一个数字
        for (int first = 0; first < nums.length - 2; first++) {
            // 不容许反复
            if (first > 0 && nums[first] == nums[first - 1]) {continue;}
            int third = nums.length - 1;
            for (int second = first + 1; second < nums.length - 1; second++) {
                // 不容许反复
                if (second > first + 1 && nums[second] == nums[second - 1]) {continue;}

                // second 和 third 2 个从两边一起向两头遍历，这样就缩小了一层循环
                while (second < third && nums[first] + nums[second] + nums[third] > 0) {
                    // 当 3 个数之和大于 0 时，将 third 往左移取更小的数，直到 second >= third
                    third--;
                }

                // 不存在符合条件的元组
                if (second == third) {break;}

                if (nums[first] + nums[second] + nums[third] == 0) {ArrayList<Integer> temp = new ArrayList<>();
                    temp.add(nums[first]);
                    temp.add(nums[second]);
                    temp.add(nums[third]);
                    result.add(temp);
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {int[] nums = new int[]{-1, 0, 1, 2, -1, -4, -2, -3, 3, 0, 4};
        List<List<Integer>> lists = threeSum(nums);
        for (List<Integer> list : lists) {for (Integer integer : list) {System.out.print(integer + "/");
            }
            System.out.println();}

        System.out.println();

        List<List<Integer>> lists2 = threeSum1(nums);
        for (List<Integer> list : lists2) {for (Integer integer : list) {System.out.print(integer + "/");
            }
            System.out.println();}
    }
}