LeetCode-015- Sum of three numbers

The sum of three number

Given an array containing n integers, determine whether there are three elements a, B, and c in nums such that a + b + c = 0. Please find all the triples that sum to 0 and are not repeated.

Note: Repeated triples cannot be included in the answer.

Examples can be found on the LeetCode website.

Source: LeetCode link: leetcode-cn.com/problems/3s… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Solution 1: brute force cracking method

First, sort the array nums, and then obtain the qualified triplet through triple traversal. In the middle, the repeated triples need to be filtered by judgment.

Solution two: double pointer method

Nums = first; nums = second; nums = third; Until second is not less than third.

The second method has one less layer of circulation than the first method, so it is much more efficient.

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

public class Solution {
    /** * Method 1: brute force method **@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;
        // Level 1 loop: iterate over the first number
        for (int first = 0; first < nums.length - 2; first++) {
            if (nums[first] > 0) {
                return result;
            }
            // Repeat is not allowed
            if (count > 0 && nums[first] == result.get(count - 1).get(0)) {
                continue;
            }
            // Second loop: iterate over the second number
            for (int second = first + 1; second < nums.length - 1; second++) {
                // The sum of the two digits is already greater than 0, so it is meaningless to iterate over the third digit
                if (nums[first] + nums[second] > 0) {
                    break;
                }
                // third loop: iterate over the third number
                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);
        // Level 1 loop: iterate over the first number
        for (int first = 0; first < nums.length - 2; first++) {
            // Repeat is not allowed
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }
            int third = nums.length - 1;
            for (int second = first + 1; second < nums.length - 1; second++) {
                // Repeat is not allowed
                if (second > first + 1 && nums[second] == nums[second - 1]) {
                    continue;
                }

                // The second and the third are traversed from both sides to the middle, thus reducing the loop layer
                while (second < third && nums[first] + nums[second] + nums[third] > 0) {
                    // When the sum of the three numbers is greater than 0, move third to the left for a smaller number until second >= third
                    third--;
                }

                // No tuple exists
                if (second == third) {
                    break;
                }

                if (nums[first] + nums[second] + nums[third] == 0) {
                    ArrayList<Integer> temp = newArrayList<>(); 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(); }}}Copy the code