For 3 minutes a day, take the algorithmic counterattack route.

Handled in the collection

A daily collection of LeetCode preambles

Code warehouse

Making: github.com/meteor1993/…

Gitee: gitee.com/inwsy/LeetC…

Title: Sum of three numbers

Difficulty: Medium

Title source: leetcode-cn.com/problems/3s…

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 meet the criteria and are not duplicated.

Note: Repeated triples cannot be included in the answer.

Example:

A given array nums = [1, 0, 1, 2, 1, 4], meet the requirements of the ternary group collection: [[- 1, 0, 1], [1, 1, 2]]Copy the code

Their thinking

I’ve been writing a series of articles about JVM and Tomcat for some time, so I’m going to pick up the topic today.

First of all, this problem is my first response is a set of three loops, must go, time complexity is O (n ^ 3), on the power button, according to the usual urine result must be a timeout, the plan I have been too lazy to write now (yes, I now is so gone with the wind), in addition to exercising the ability of writing code, with algorithms like nothing.

The other plan can’t come out again, have no way, can only turn over the answer.

The first thing you do is sort the array, make it an ordered array.

If you add up all three numbers and you get 0, there’s a special case where 0 plus 0 plus 0 is 0.

If you take that out of the equation, the first digit must be negative, the second digit must be larger than the first digit, and the third digit must be larger than the second digit.

Apply the above special case, then there will be a certain relation A <= b <= c.

If I get to this point, I still haven’t gotten out of the triple loop, so I’m still O(n^3), which is definitely not going to work, and I still need to optimize.

Aims to reduce the time complexity to O (n ^ 2), it is dual loop to do all the things, the outermost layer of the circulation loop is to find a, this is inevitable, can play the prick is only the first double loop, in the process of looking for b and c, trying to find the inner link, in a loop, I’m just going to find b and C.

If we fix a and b, then there’s only one unique c that satisfies a plus b plus c is equal to 0. When the second loop repeats b1, if a plus b1 plus c1 is equal to 0, then c1 has to be smaller than c.

So that we can be in the second cycle to consider a double pointer, from small to large, arrange an array from small to large, from when we get b in c when we from big to small to pick up, at this time, we take the b and c are tied in the second, so we forced the triple loop became a twofold reduction cycle.

B and C here can be abstracted into two Pointers, the left pointer and the right pointer, the left pointer can move one bit to the right, and the right pointer can move n bits to the left, depending on the elements of the array, in the worst case n moves, so the time complexity is also O(n), the first loop has another O(n), So the overall time is O(n^2).

Code:

public List<List<Integer>> threeSum(int[] nums) {
    int n = nums.length;
    Arrays.sort(nums);
    List<List<Integer>> ans = new ArrayList<>();
    // The outermost loop, iteration A
    for (int a = 0; a < n; ++a) {
        // Because elements cannot be repeated, the same direct next loop is encountered
        if (a > 0 && nums[a] == nums[a - 1]) {
            continue;
        }
        // the pointer to c starts at the rightmost end of the array
        int c = n - 1;
        int target = -nums[a];
        B / / iteration
        for (int b = a + 1; b < n; ++b) {
            // Check if it is the same as the last iteration
            if (b > a + 1 && nums[b] == nums[b - 1]) {
                continue;
            }
            // B is positioned to the left of C
            while (b < c && nums[b] + nums[c] > target) {
                --c;
            }
            // If the pointer overlaps, we can exit the loop, indicating that the corresponding c is not found
            if (b == c) {
                break;
            }
            // If the sum of b and c is equal to -a, then we have found the final result
            if (nums[b] + nums[c] == target) {
                List<Integer> list = newArrayList<>(); list.add(nums[a]); list.add(nums[b]); list.add(nums[c]); ans.add(list); }}}return ans;
}
Copy the code

I don’t know if you still remember the solution of the sum of the two numbers before, when we determine a and B, we can put the entire array in a hash table when we finally look for C, and judge whether c exists by the characteristics of the hash table. If not, we will enter the next cycle.

This article is constantly updated, you can search “Geek excavator” on wechat to read it in the first time, and the key words in reply have all kinds of tutorials PREPARED by me, welcome to read.