preface

Give you an array num containing n integers. Judge whether there are three elements a, b and c in num, so that a + b + c = 0? Please find all triples with sum 0 and no repetition.

Note: the answer cannot contain repeated ternary

1, Violent solution

Seeing that the problem is summed according to conditions, the first thing I think of is the violent solution, traversing the array, Find data suitable for conditions (I'm ashamed. I can only solve the problem first and then optimize the problem). When I put it into practice, the violent solution is indeed logical and written quickly, but there are problems. The problem requires that there can be no repeated solutions. I use the violent solution. Cutting and solving are all solutions, which is inevitable to be repeated. I try some solutions, but it's still not very good, only After looking at the problem solution, I found that the big guys are big guys. Using the sorting and double pointer algorithm, the logic is easy to understand, and the problem is perfectly solved. I won't post it to make a fool of myself.

2, Sorting + double pointer solution

1. Sort + double pointer

The difficulty of this problem is how to remove repeated solutions.

Algorithm flow:
1. Special judgment: for the array length nn, if the array is null or the array length is less than 3, return [].
2. Sort the array.
3. After traversing the sorted array:
4. If num [i] > 0: because it has been sorted, it is impossible for the sum of three numbers to be equal to 00, and the result will be returned directly.
5. For duplicate elements: skip to avoid duplicate solutions
Make the left pointer L=i+1 and the right pointer R=n-1. When l < R, execute the cycle:
6. When nums[i]+nums[L]+nums[R]==0, execute the loop to judge whether the left and right bounds are repeated with the next position and remove the repeated solution. At the same time, l and R are moved to the next position to find a new solution
If the sum is greater than 00, it means that num [R] num [R] is too large and R moves left
If the sum is less than 00, it means that num [L] num [L] is too small, and L moves to the right

Ternary sorting double pointer algorithm flow

The code is as follows (example):

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        
        n=len(nums)
        res=[]
        if(not nums or n<3):
            return []
        nums.sort()
        res=[]
        for i in range(n):
            if(nums[i]>0):
                return res
            if(i>0 and nums[i]==nums[i-1]):
                continue
            L=i+1
            R=n-1
            while(L<R):
                if(nums[i]+nums[L]+nums[R]==0):
                    res.append([nums[i],nums[L],nums[R]])
                    while(L<R and nums[L]==nums[L+1]):
                        L=L+1
                    while(L<R and nums[R]==nums[R-1]):
                        R=R-1
                    L=L+1
                    R=R-1
                elif(nums[i]+nums[L]+nums[R]>0):
                    R=R-1
                else:
                    L=L+1
        return res

Author: wu_yan_zu
 Link: https://leetcode-cn.com/problems/3sum/solution/pai-xu-shuang-zhi-zhen-zhu-xing-jie-shi-python3-by/
Source: force buckle( LeetCode)
The copyright belongs to the author. For commercial reprint, please contact the author for authorization, and for non-commercial reprint, please indicate the source.

2.C + + version

The boss wrote the solution ideas and python routines. If I can't do it yet, it's too embarrassing. I refer to the C + + version written by a big brother in the solution comments, and I also passed the problem with C + +. (simply add some notes, which is better to match the ideas.).
The code is as follows (example):

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
       vector<vector<int>> ans;
       //If there are less than 3 elements in the array, it is returned directly
       if(nums.size()<3)return ans;
       //Array sorting
       sort(nums.begin(),nums.end());
       //After sorting, if all numbers are positive, then the sum of three numbers cannot be zero
       if(nums[0]>0)return ans;
       int i = 0;
       while(i < nums.size()){
           if(nums[i]>0)break;
           int Left = i+1;
           int Right = nums.size()-1;
           
           while(Left < Right){
               //Anti overflow
                long long x = static_cast<long long>(nums[i]);
                long long y = static_cast<long long>(nums[Left]);
                long long z = static_cast<long long>(nums[Right]);

                if(x+y+z>0){
                    Right--;
                }else if(x+y+z<0){
                    Left++;
                }else{
                    ans.push_back({nums[i],nums[Left],nums[Right]});
                    //Avoid repeating elements that cause repeated solutions
                    while(Left<Right&&nums[Left] == nums[Left+1]){
                         Left++;
                    }
                    while(Left<Right&&nums[Right] == nums[Right-1]){
                        Right--;
                    }
                  
                    Left++;
                    Right--;
                }
              
           }
             while(i<nums.size()-1&&nums[i]==nums[i+1]){
                        i++;
                    }
             i++;

   }
           return ans; 
       }

};

summary

1. As a future embedded engineer, I may use more C and more basic syntax of C. However, for these object-oriented, they only know some basic syntax, more function libraries and various encapsulated library functions, and they use these library functions to find that direct call is true.

2. In learning embedded engineering, there may not be much use for algorithms, but learning some algorithms can improve personal four bits and the way to solve problems. It is important to try to use other methods to solve a problem in a project. The way to solve problems is updated from generation to generation, and people are making continuous progress.

3. In fact, learning some algorithms is also to understand the way of computer thinking. For a problem, I think it is better to solve the problem first and then optimize the problem. Of course, for people with certain strength, solving while optimizing is a better choice. Understanding computer thinking can better optimize the code you write. Therefore, learning algorithm is also very important and essential.

4. On the way to study, you and I encourage each other.