Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Recommended reading

  • CSDN home page
  • GitHub open source address
  • Unity3D plugin sharing
  • Jane’s address book
  • My personal blog
  • QQ group: 1040082875

Hello, everyone, I am a little Magic dragon, Unity3D software engineer, VR, AR, virtual simulation direction, update software development skills from time to time, life perception, remember to use one button three links.

A, the title

1. Algorithm topic

“Find an array of integers where the sum of three integers equals zero.”

Title link: Source: LeetCode

Link: 15. Sum of three numbers – LeetCode (leetcode-cn.com)

2

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, 0, 1]]Copy the code
Example 2: Input: nums = [0] Output: []Copy the code

Second, the problem solving

1. Analysis of ideas

Find all non-repeating triples that sum to 0. This non-repetition requires that we cannot enumerate all triples using a violent triple loop (of course, doing so would result in a timeout).

Because the double loop has elements A and B, there will be only one and only c that a+b+c=0, so the double loop stays the same, and the third loop becomes a pointer that moves from the right end of the array, so that we can find the last element c. The algorithm complexity is O(N2).

Of course, this algorithm can be optimized, because it can’t be repeated, so you can just loop through a layer, check for element A, and then use two Pointers to the left and right of the array, and verify that the sum of the three numbers is zero, save it if it is, and move the pointer if it is not.

2. Code implementation

The first step is sorting, and the second step is to find the solution using the two-pointer method.

public class Solution {
    public IList<IList<int>> ThreeSum(int[] nums) {
        IList<IList<int>> result = new List<IList<int> > ();int len = nums.Length;
        if (len < 3) return result;
        Array.Sort(nums);
        for (int i = 0; i < len - 2; i++)
        {
            if (nums[i] > 0) break;
            if (i > 0 && nums[i] == nums[i - 1]) continue; / / to heavy
            int left = i + 1;
            int right = len - 1;
            while (left < right)
            {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == 0)
                {
                    result.Add(new List<int>() { nums[i], nums[left], nums[right] });
                    while (left < right && nums[left] == nums[left + 1]) left++; / / to heavy
                    while (left < right && nums[right] == nums[right - 1]) right--; / / to heavy
                    left++;
                    right--;
                }
                else if (sum < 0) left++;
                else if (sum > 0) right--; }}returnresult; }}Copy the code

3. Time complexity

Time complexity: O(N)

N is the length of the array nums

Space complexity: O(log N)

We ignore the space to store the answers, and the space complexity of the extra sort is O(logN). However, we have modified the input array nums, which is not necessarily allowed in practice, so it can also be regarded as using an additional array to store and sort copies of NUMs, with space complexity O(N).

Third, summary

This problem is similar to the first problem to find the sum of even numbers. Both of them use a double pointer, and then point to the head and tail respectively, and then move the pointer according to the situation.

Of course there is a big difference.