leetcode 1.Two Sum

In the process of preparing for Internet recruitment, leetcode and sword-finger offer are standard. Although I have written 200 questions so far, I have forgotten a lot of ideas or couldn’t pass the free bug once when I wrote the code. So I summarized them slowly from the beginning.If you have any questions, I hope you can communicate under the comments, and I’d be happy to communicate with you, to learn together, to take the BAT ATM. Maybe some people would say that there are enough solutions now, but this blog is part of a record of personal growth, and it’s the one that you want to use most.Simple language and analysis can help you start the leetcode brush trip.

It must be hard and lonely to prepare for a job. Every day you have to run a job fair and learn to organize and collect information. It’s as hard and hard as hiking in the desert. Although you are often disappointed, you still have expectations. I believe you can be your God and get something in the end if you persist. All right, no more.Then we’ll add the chicken soup and start a new journey.

Link: https://leetcode.com/problems/two-sum/description/

Implication: Find a pair of values in a given array so that the sum of the two numbers is the target value, and the final answer is to return the subscript.

Key points: This problem is categorized as an “array, hash table” problem, where hash tables use key-value mapping pairs, keys can be of one type or combinations of many types, such as pairs & lt, int, string, etc. can be seen in later topics.> the form of the composite key. As a common data structure, hash table has the advantage of providing insert and delete operations with constant O (1) time complexity. Therefore, a hash table can be considered when a violent law is overdue and a large number of intermediate repetitive results are used.For example, if you keep the median value of dynamic programming in later problems, you can avoid a lot of computation.

So the simplest and most violent way is the two for cycle of O (n^2), which takes 128ms time.

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> res;
        for(int i=0;i<nums.size();i++)
        {
            for(int j=i+1;j<nums.size();j++)
            {
                if(nums[i]+nums[j]==target)
                {
                    res.push_back(i);
                    res.push_back(j);
                    return res;
                }
            }
        }
    }
};

The map. count function looks for the number of elements to be looked up in the hash table, and returns 1 if it does, or 0 if it doesn’t.So the return value can only be 1 or 0.。 There is another way.To find out if the primary key exists, use the map. find function to return the location of the element being looked up, or map. end () if not, because the find function returns the iterator, you need to construct the iterator in advance, such as it in the annotation.

So looking for a hash table to see if it’s possible to use two conditions: map. count ()? 0 or map. find ()? Map. end ().

This method is O (n), because the insertion and search in the hash table are o (1), and the time is 8ms.

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> res;
        map<int,int> mp;
　　　　 // map<int, int>::iterator it Structural iteratorfor(int i=0;i<nums.size();i++) mp[nums[i]]=i;
        for(int i=0;i<nums.size();i++)
        {
            int search=target-nums[i];
　　　　　　　// it=mp.find(search);
　　　　　　　// if(it!=mp.end() && i!=mp[search]) When you use the find function, you should also pay attention to the special case. A number has been used two times, such as 6=3+3.

            if(mp.count(search) && i!=mp[search])
            {
                res.push_back(i);
                res.push_back(mp[search]);
                break;
            }
        }
        return res;
    }
};

In fact, the above method can be optimized to use only one loop, so that special cases do not have to be judged separately, but if the subscript needs to be output according to [small, large] needs to pay attention to the corresponding order. The time is 4ms.

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> res;
        map<int,int> mp;
        for(int i=0;i<nums.size();i++)
        {
            int search=target-nums[i];
            if(mp.count(search))
            {
                res.push_back(mp[search]);
                res.push_back(i);
                break;
            }
            mp[nums[i]]=i;
        }
        return res;
    }
};