Leetcode question 1: sum of two numbers (3 languages)

Hello everyone , I meet you again , I'm your friend, Quan Jun .

Leetcode The first question is ： Sum of two numbers

Given an array of integers nums And a target value target, Please find the sum in the array as the target value Two Integers . You can assume that each input corresponds to only one answer . however , You can't reuse the same elements in this array . Example : Given nums = [2, 7, 11, 15], target = 9 because nums[0] + nums[1] = 2 + 7 = 9 So back [0, 1]

mark ： Only in Python The solution is analyzed in detail ,c++ And java If there is no special place that needs attention, do not analyze .

One 、Python solution

solution 2,3 Refer to the linfeng886 The blog of

solution 1： Violent search

class Solution:
    def twoSum(self, nums, target):
        """ :type nums: List[int] :type target: int :rtype: List[int] """
        # Yes nums Cycle per element 
        for i in range(len(nums)):
        # from nums[i] Next start looking 
            for j in range(i+1,len(nums)):
            # If found, return the value 
                if nums[i]+nums[j]==target:
                    return i,j

Copy

analysis ： The code is very simple , First of all, use i Loop through the array , At every i Under the cycle , Look for the remaining elements target-nums[i] Value . If you find it , Just return i,j Two Numbers .（ The program assumes that it can be found ） Let's see the results ：

We can see that the efficiency is very low , The main reason is to use two for loop , The time complexity is O(n2).

solution 2： once for loop

 Code that made a small mistake at the beginning 

Copy

class Solution:
    def twoSum(self, nums, target):
        """ :type nums: List[int] :type target: int :rtype: List[int] """
        # Directly in i One by one , Direct judgment target-nums[i] In the list , In the case of list.index() Get index , I used it once for loop . great .
        for i in range(len(nums)):
            if target-nums[i] in nums:
                return i,nums.index(target-nums[i])

Copy

The problem with this code is ：

We can see , Forget the rule that an element can only be used once , So make a judgment . Revised edition ：

class Solution:
    def twoSum(self, nums, target):
        """ :type nums: List[int] :type target: int :rtype: List[int] """
        for i in range(len(nums)):
            if target-nums[i] in nums:
            # Added the judgment that the two returned numbers cannot be the same in the following table 
                if i!=nums.index(target-nums[i]):
                    return i,nums.index(target-nums[i])

Copy

You can see ： The speed has increased several times . It's not bad . But by checking the official answer reference linfeng886 The blog of Know that there is a faster way —- be based on hash table Solutions for .

solution 3： be based on Python Dictionary search

About hash table( Hashtable ), Simply put, there are key value pairs key,value A data structure of , For those familiar with Python For people who , A common dictionary is a kind of hash table. Its search speed is very fast , It can be understood as O(1). So this is equivalent to solving 2 An improvement is made on the basis of . solution 2 On the premise that space remains unchanged , stay i loop , Directly search the list for target-nums[0] The elements of , And the search speed of the list is far less than hash table. So the key of solution three is , The task of searching is carried out in the dictionary instead of list In the middle of ( It is open to question. ) Code ：

class Solution:
    def twoSum(self, nums, target):
        """ :type nums: List[int] :type target: int :rtype: List[int] """
        # Traverse a i, Just put nums[i] Put it in the dictionary . after i Keep adding , Always meet 
        #target - nums[i] In the dictionary . When you meet return that will do . Notice here first return Yes. dict[a], Then the current i, The reason is that dict What's in there value It's all traversed before i, So it's better than the current i Small , According to the order from small to large, so it's arranged like this .
        dict = { 
   }
        for i in range(len(nums)):
            a = target - nums[i]
            if a in dict:
                return dict[a],i
            else:
                dict[nums[i]] = i

Copy

Running results ：

As you can see from the code , solution 3 Is to find out what you need target-nums[i] From solution 2 in list Turned into dict nothing more , But the results have improved significantly . But here's the thing , Here we use space and practice to make a tradeoff, That is to say, the solution 3 It's a lot faster , But the space needed adds a new dict. This also gives us a hint ： In the future, if you encounter similar elements that need to be searched through , Please refer to this example , utilize hash table lookup .

Two 、Java solution

solution 2,3 Refer to the official solution twosum as well as Novice tutorial java Array section Pythonliast And java Array difference https://blog.csdn.net/wu1226419614/article/details/80870120 About hashmap data type https://www.cnblogs.com/hello-yz/p/3712610.html

solution 1： Violent search

Code ：

class Solution { 
   
    public int[] twoSum(int[] nums, int target) { 
   
        int[] a = new int[2];
        for(int i=0;i<nums.length;i++){ 
   
            for(int j=i+1;j<nums.length;j++){ 
   
                if(nums[i]+nums[j]==target){ 
   
                    a[0] = i;
                    a[1] = j;
                 //return new int[] {i,j}; 
                }
            }
        }
        return a;
    }
}

Copy

There is no special explanation here . I just want to mention about return new int[] {i,j} A little explanation of . This kind of writing is given by the official interpretation . Reference resources Rookie tutorial on array interpretation , You can know that this is a way of function input parameters or return values . meanwhile , The official solution will be at the end of the class throw An exception , If it is deleted, an error will be reported , because throw It's also return An alternative form of .( That is to say, even if this class says no at the beginning void Of , To return to a int[] Or something , But the syntax of throwing an exception at the end is consistent .) For this example , The execution will start from if Under the return Leave the program , So no exceptions will be thrown .

solution 2： two for loop （ Two times hashmap）

Here and Python Of 3 Make a comparison between two solutions . You can see the solution of two languages 1 It's exactly the same . But the solution 2 On , There will be some differences . Then the solution 3 It's exactly the same again . Why the solution 2 Hui He Python solution 2 What's the difference ？ Look back at Python solution 2： adopt i Loop list , Direct judgment target – nums[i] Whether it's on the list , If you are , Go straight back i, And list.index(target-nums[I]). Here we use Python Built in functions index. You can easily get the index , And for java Array of , It is not so convenient to get the index of array elements . Here is a good comparison , From which we can know java For arrays, there is a binarySearch How to find , And it is implemented by dichotomy , So it only applies to ordered arrays . At the same time, if you use it again for Get index circularly , Do more harm than good . It's better to use it again for Loop to match the index with the value one by one , Use similar Python Dictionary way , This makes it faster to find —–hashmap Code ：

class Solution { 
   
    public int[] twoSum(int[] nums, int target) { 
   
        int[] b = new int[2];
        HashMap<Integer,Integer> map = new HashMap<Integer,Integer>(); 
        for(int i=0;i<nums.length;i++){ 
   
            map.put(nums[i],i);
        }
        for(int j=0;j<nums.length;j++){ 
   
            int a = target - nums[j];
            if(map.containsKey(a) && j!=map.get(a)){ 
   
                b[0] = j;
                b[1] = map.get(a);
                    return b;
                 //return new int[] {j,map.get(a)};
            }
        }
    return b;
}
}

Copy

Here are some points to pay attention to ： 1.HashMap<Integer,Integer> = new HshMap<Integer,Integer>() there Integer Cannot use basic data type int. You can see here . 2.hashmap Declaration definition format , Just like the instantiation of general classes . class1 xx = new class1() 3.hashmap And hashtable.hashmap It can be basically equivalent to hashtable. And it can be seen as an upgraded version .HashMap Almost equal to Hashtable, except HashMap Right and wrong synchronized Of , And can accept null(HashMap It can be accepted as null Key value of (key) And the value (value), and Hashtable No way. ). Details can be found at http://www.importnew.com/7010.html . 4.hashmap Of put,get They are deposit and withdrawal . as well as containsKey It is reflected in the code , It's easy to understand . 5. Be careful if In judgment &&（ Short circuit operator ） Can not be & Instead of , Can pass LeetCode A simple example of , But an error will be reported when submitting . analysis ：& Even if the front is false, The logical expression behind the operator will still be judged . And the latter is j != map.get(a). Probably a It doesn't exist , Therefore, complains . take map.get（a） Printed out is a null The pointer . Further explanation , For operation & Your code will report an error ： Exception in thread “main” java.lang.NullPointerException This is the null pointer exception . Explanation is ” The program encountered a null pointer ”. To put it simply, an uninitialized or nonexistent object is called , This error often occurs in creating images , Call arrays in these operations , For example, the image is not initialized , Or the path error when creating the image, etc . Null pointer in array operation . The initialization of an array is to allocate the required space to the array , And the initialized array , The elements are not instantiated , It's still empty , So you also need to initialize every element （ If you want to call ). See https://zhidao.baidu.com/question/494551043.html however , It's all in python Is allowed .

solution 3： once for loop （ once hashmap）

This solution idea is similar to Python solution 3 cut from the same cloth , It's exactly the same , The only difference is that Python Use a dictionary to find ,Java Use HashMap Do the search . Therefore, this solution will not be explained too much . Code ：

class Solution { 
   
    public int[] twoSum(int[] nums, int target) { 
   
        HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
        for(int i=0;i<nums.length;i++){ 
   
            if(map.containsKey(nums[i])){ 
   
                return new int[] { 
   map.get(nums[i]),i};
            }
            map.put(target-nums[i],i);
        }
        return new int[]{ 
   1,1,1};
    }
}

Copy

You can see , And solution 2 Compared with the speed, the improvement is limited . What needs to be noted here is ：1. The last line of code doesn't matter return What is the （ It must be an array ） indifferent , Because I won't go this far , But the optimal solution is better to throw an exception like the official solution . Because if you really get to this point , It means that there must be an exception in the program . 2. What I write here is slightly different from the official interpretation , It's the same thing . I put put The entered value is replaced by target-nums[i]. And then determine nums[i] Whether in map in , Let's not be specific , A little fussy .

3、 ... and 、C++ solution

With the above two language solutions to pave the way , I think C++ The solution idea will be much clearer .

solution 1： Violent search

Look directly at the code ：

class Solution { 
   
public:
    vector<int> twoSum(vector<int>& nums, int target) { 
   
        //vector The type is an array with variable length , More flexible . need #include<vector>
        vector<int> a;
        //int a[2]; The specified return here is verctor type , Therefore, ordinary arrays cannot be used here array
        for(int i=0;i<nums.size();i++){ 
   
            for(int j =i+1;j<nums.size();j++){ 
   
                if(nums[i]+nums[j]==target){ 
   
                    // stay a Last element added 
                    a.push_back(i);
                    a.push_back(j);
                    //a[0] = i;
                    //a[1] =j;
                    return a;
                }
            }
        }
    // Notice here and java Dissimilarity , There is no need to return one vector 了 . Although this class requires a return value 
    }
};

Copy

Here are some notes ： 1. Find array length . Python：len(list); java:nums.length; c++:nums.size() 2.java And c++ The length of the basic array type of is immutable , It requires flexible use vector Instead of . About arrays and vector stay c++ And Java The use of c++ Related see Novice tutorial Java Of vector See zheting The blog of The important point is posted ： java Use needs import java.util.Vector; Insert function ： public final synchronized void adddElement(Object obj) take obj Insert the tail of the vector .obj It can be any kind of object . For the same vector object , You can also insert different objects into it . However, you should insert an object instead of a value , So when inserting values, you should pay attention to converting the array into the corresponding object . for example ： To insert an integer 1 when , Don't call directly v1.addElement(1), The right way is ：

Vector v1 = new Vector(); 
Integer integer1 = new Integer(1); 
v1.addElement(integer1); 

Copy

3. About arrays as formal parameters of functions . In this case, it is written like this ：

vector<int> twoSum(vector<int>& nums, int target) { 
   
//insert your code
}

Copy

Or write like this ：

vector<int> twoSum(vector<int> &nums, int target) { 
   
//insert your code
}

Copy

perhaps ：

vector<int> twoSum(vector<int> nums, int target) { 
   
//insert your code
}

Copy

See the rookie tutorial for details Explanation of array as formal parameter

solution 2： two map( Non hash table )

Note here that c++ Of map Realized key,value pairing . and c++ There is also hash_map, namely hash table. The difference between them is ： hash_map use hash Table is stored ,map Generally, red and black trees are used (RB Tree) Realization . Therefore, its memory data structure is different . See the specific differences between the two zhenyusoso The blog of And Miles- The blog of . First look map Implemented code ：

class Solution { 
   
public:
    vector<int> twoSum(vector<int>& nums, int target) { 
   
        vector<int> a;
        map<int,int> map;
        //hash_map<int,int> hp;
        for(int i=0;i<nums.size();i++){ 
   
           map[nums[i]] = i;
            
        }
        for(int j=0;j<nums.size();j++){ 
   
            if(map.count(target-nums[j])==1 && map[target-nums[j]]!=j){ 
   
                a.push_back(j);
                a.push_back(map[target-nums[j]]);
                return a;
            }
        }
    return a;
    }
};

Copy

Do some analysis ： 1. This method and java Solution method 2 The version is very close . The main difference is java Of hashmap The methods called are ：put(key,value),get(key),containsKey() and c++ Of map Find whether the key value is count. About map Of count And find It's a very common method , They are used for the same purpose . Specific view Andy Niu The blog of . 2. It's used here map, Why not hash_map Class ？ I am here xcode Implemented once in ,macos The system is about hash_map The statement of is quite special ：

#if defined __GNUC__ || defined __APPLE__
#include <ext/hash_map>
#else
#include <hash_map>
#endif
int main()
{ 
   
        using namespace __gnu_cxx;

        hash_map<int, int> map;
}

Copy

Simultaneous use find Method to distinguish hash_map Whether it contains what you want key.

hash_map<int,int> hp;
if(hp.find(target-nums[j])!=hp.end() && hp[target-nums[j]]!=j){ 
   
// Code section 
}

Copy

solution 3：1 Time map( Non hash table )

There is nothing to analyze , It is the same as the solution of Trinity module in the above two languages .

class Solution { 
   
public:
    vector<int> twoSum(vector<int>& nums, int target) { 
   
        vector<int> a;
        map<int,int> map;
        for(int i=0;i<nums.size();i++){ 
   
            if(map.find(target-nums[i])!=map.end()){ 
   
                a.push_back(map[target-nums[i]]);
                a.push_back(i);
                return a;
            }
            else{ 
   
                map[nums[i]] = i;
            }
        }
         return a;
        }
    

};

Copy

The code here uses map Of find instead of count To judge map Whether it contains the specified key.

ps: The following notes should 3 The two languages are recorded separately , Such an article is too long , Prone to boredom .

Publisher ： Full stack programmer stack length , Reprint please indicate the source ：https://javaforall.cn/131493.html Link to the original text ：https://javaforall.cn