We need to find all the triples in an array where the sum of the three numbers is 0. In fact, we can think of two double Pointers and then combine them to get a result equal to the desired value. If a + b + c = n, and n is an incoming variable, the idea is the same. If the result set cannot be repeated, the most common way is to do it directly by sorting, so that when taking the data, we can directly judge whether we have taken it or not, and skip the data once we have taken it. Let’s take a look at the specific problems and solve the problem analysis

The sum of three number

The title

Given an array nums containing n integers, determine if 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.

Example 1:

Input: nums = [1, 2, 1, 4] output: [[1, 1, 2], [1, 1]]

Example 2:

Nums = [] Output: []

Example 3:

Input: nums = [0]

Tip:

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

Subject analysis

1

Time complexity: O(N *N *N)

Space complexity: O(1)

It’s computed directly through the triple loop.

2. Optimize your thinking

Time complexity: O(N *N *N)

Space complexity: O(logN)

Key: sort + double pointer.

We can sort the entire array of inputs first to prevent duplication.

The idea of choosing a double pointer is that the sum of our three numbers can actually take out a number first, and then treat it as the sum of two numbers, so that we can flexibly use the idea of a double pointer.

Pointer movement during a two-pointer process. A, B, and C subscripts.

• The subscript A needs to traverse the number set, and the sum of B + C is equal to -1 * a, which needs to judge whether it is repeated by the previous one, and skip if it already exists.
• In the process of moving the double Pointers of B and C, first b pointer is initialized and a subscript + 1; And judge whether there is duplication of data by the previous number, if there is already, skip.
• The initial pointer position of the c pointer is nums.length-1. If a + b > -a then we need to move c to the left, otherwise we need to move B to the right, because we already sorted.
• If a + b == -a, the true result is found and stored in the returned result set.
• If the c pointer == b pointer indicates that the search has been completed, the loop is closed and the a pointer is moved back.

The problem solving code

public class NumThreeSumTest {

    public static void main(String[] args) {
        NumThreeSumTest numThreeSumTest = new NumThreeSumTest();
        List<List<Integer>> lists = numThreeSumTest.threeSum(new int[] {-1.0.1.2, -1, -4});
        System.out.println(lists);
    }

    public List<List<Integer>> threeSum(int[] nums) {
        // Array length
        int len = nums.length;
        / / sorting
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();

        for (int first = 0; first < len; first++) {
            // Skip the same value
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }
            int third = len - 1;
            int target = -nums[first];
            for (int second = first + 1; second < len; second++) {

                // Skip the same value
                if (second > first + 1 && nums[second] == nums[second - 1]) {
                    continue;
                }
                // Make sure b is to the left of C
                while (second < third && nums[second] + nums[third] > target) {
                    --third;
                }
                // If the Pointers overlap, then b continues to increment
                // If a + b + c = 0 and b < c, exit the loop
                if (second == third) {
                    break;
                }

                // Find the appropriate solution and put it in the result set
                if(nums[second] + nums[third] == target) { result.add(Arrays.asList(nums[first], nums[second], nums[third])); }}}returnresult; }}Copy the code

The resources

Leetcode-cn.com/problems/3s…