【LeetCode.1】Two Sum （C++）

缺乏、安全感 2022-04-24 21:36 140阅读 0赞

# 问题描述 #

> Given an array of integers, return indices of the two numbers such that they add up to a specific target.  
> You may assume that each input would have exactly one solution, and you may not use the same element twice.

# 示例 #

> Given nums = \[2, 7, 11, 15\], target = 9,  
> Because nums\[0\] + nums\[1\] = 2 + 7 = 9,  
> return \[0, 1\].

这道题其实我以前做过了，但都不是用c++实现的，所以现在就是刷题顺便练习C++了。

# 思路 #

循环遍历这个数组，再新建一个map对象，每遍历一个数组元素时，先判断target减去数组元素的差值是否已经在map中了，否则就往map对象中添加pair(数组元素，数组索引)。  
因为map中查找是否存在，是查找的key，所以key必须存数组元素，而不是数组索引。

# 代码 #

class Solution { 
    public:
        vector<int> twoSum(vector<int>& nums, int target) { 
            vector<int> res;
            map<int,int> hash;
            for(int i=0;i<nums.size();i++){ 
                if(hash.find(target-nums[i]) != hash.end()){ 
                    //因为要寻找差值，所以key必须存数，而不是索引
                    res.push_back(i);
                    res.push_back(hash[ target-nums[i] ]);
                    return res;
                }
                hash[nums[i]] = i;
            }
            return res;
            //注意最后这句得加，不然报错control reaches end of non-void function
        }
    };

map对象创建用的是`map<int,int> hash;`，所以调用函数时用`.`，且可以使用下标操作来insert值，和取value。

class Solution { 
    public:
        vector<int> twoSum(vector<int>& nums, int target) { 
            vector<int> res;
            map<int,int> *hash = new map<int,int>();
            for(int i=0;i<nums.size();i++){ 
                if(hash->find(target-nums[i]) != hash->end()){ 
                    //因为要寻找差值，所以key必须存数，而不是索引
                    res.push_back(i);
                    res.push_back(hash->at(target-nums[i] ));
                    return res;
                }
                hash->insert({ nums[i], i});
            }
            return res;
        }
    };

map对象创建用的是`map<int,int> *hash = new map<int,int>();`，所以调用函数时用`->`（因为这里是map指针），且不可以使用下标操作，insert值用`->insert()`，取value用`->at()`。

对于第一种代码，在栈中开辟了map对象所需要的内存空间。更深入的说，当此代码结束后，内存会自动释放。  
对于第二种代码，在栈中开辟了一个指针所需要的内存空间，且在堆中开辟了map对象所需要的内存空间。更深入的说，当此代码结束后，仍需要手动delete释放内存，且让指针= null。

# 8ms submission #

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

这是最快的代码，没什么不同的，但是这里map用的是c++11新出现的unordered\_map，底层实现不再是有序的红黑树了，而是哈希桶实现，这使得这种map在取value的时候的时间复杂度为 O ( 1 ) O(1) O(1)。所以在本题中，使用unordered\_map能让程序更快。