1. Sum of two numbers

Sum of two numbers (C++)

Topic introduction

 Given an array of integers  nums  And an integer target value  target, Please find... In the array   And is the target value  target   the   Two   Integers , And return their array subscripts .

 You can assume that each input corresponds to only one answer . however , The same element in the array cannot be repeated in the answer .

 You can return the answers in any order .

 source ： Power button （LeetCode）
 link ：https://leetcode-cn.com/problems/two-sum
 Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Enumeration

Core tools

• Use STL in find() and distance()

Their thinking

1. Use the target value target Subtract array vector The first element in
2. Judge whether the difference exists , And is not equal to this element ( The title requires that the same element cannot be repeated )
3. about vector The elements in perform this operation in turn

Source code of problem solving

// 2021.07.13
using namespace std;

class Solution {
    
public:
    vector<int> twoSum(vector<int>& nums, int target) {
    

        //  Sort , Easy to use binary_search() Algorithm 
        // sort(nums.begin(), nums.end()); error

        vector<int>::iterator first = nums.begin();
        
        //  Record subscripts 
        int i = -1;
        int j = -1;

        for (vector<int>::iterator it = nums.begin(); it != nums.end(); it++)
        {
    
            //  Record target The difference from the current element 
            int cha = target - (*it);

            //  If the difference exists, use cha_weizhi Save its location 
            vector<int>::iterator cha_weizhi = find(nums.begin(), nums.end(), cha);

            //  Judge whether the difference exists 
            if (cha_weizhi != nums.end() && cha_weizhi != it)
            {
    
                //  Use distance The algorithm returns the subscript 
                i = distance(first, it);
                j = distance(first, cha_weizhi);
                
                return {
    i, j};
            }

        }

      return {
    };
        

    }
};

/* *  notes ： * distance(): *  grammar ： * template<class InputIterator> * typename iterator_traits<InputIterator>::difference_type distance (InputIterator first,InputIterator last); *  This function will return [first, last) The number of elements contained in the range . */

There is an error

The sort operation caused an error

 For the use of binary_find() The algorithm improves the search speed , You need to sort the sequence 
 error ：vector The element position changes after sorting , When the subscript is returned, the subscript after sorting is returned 

Condition judgment error

 if (cha_weizhi != nums.end() && cha_weizhi != it)
  Missing in the condition judgment of this statement cha_weizhi != it 
 Make the title “ The same element in the array cannot be repeated in the answer ” Requirements not met 

hash Table method

advantage

1. Use map Find index find target - x The time complexity of is O(1), Instead, use enumeration to find target -x The time complexity of is O(N^2)
2. Using enumeration method requires judging that two numbers are not themselves , While using map Because its key value is unique , You don't have to judge

Core tools

• unordered_map : No automatic sorting map

The core idea

1. Create a unordered_map（ Sorting will change the subscript of array elements ）
2. use unordered_map Key to store vector The elements of , use unordered_map To store vector Subscript of element （ Because it is convenient to search for keys , Feel free to put elements into keys ）
3. Determine whether there is a return subscript in the difference {it->second, i}
4. Since this method does not traverse twice, there will be no problem of using the same element twice

Source code of problem solving

class Solution {
    
public:
    vector<int> twoSum(vector<int>& nums, int target) {
    
        unordered_map<int, int> hashtable;
        for (int i = 0; i < nums.size(); ++i) {
    
            auto it = hashtable.find(target - nums[i]); //  When hashtable When not assigned it = hashtable.end();
            if (it != hashtable.end()) {
    
                return {
    it->second, i};
            }
            hashtable[nums[i]] = i;	 //  about hashtable Perform assignment operation , bring vector All unqualified elements in the will put the element value in hashtabe In the key of （ Easy to find again ）, Put the subscripts in the original order hashtable Of （ Convenient return subscript ）
        }
        return {
    };
    }
};

 author ：LeetCode-Solution
 link ：https://leetcode-cn.com/problems/two-sum/solution/liang-shu-zhi-he-by-leetcode-solution/
 source ： Power button （LeetCode）
 The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source .