力扣-1题两数之和（C++）-两种方法 map和vector

Love The Way You Lie 2023-01-23 12:59 3阅读 0赞

题目链接：[https://leetcode-cn.com/problems/two-sum/][https_leetcode-cn.com_problems_two-sum]  
题目如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70 1]  
解法一：

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

解法二：  
思路：  
本题使用map，以下列出使用数组和set来做哈希法的局限。  
1、数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。  
2、set是一个集合，里面放的元素只能是一个key，而两数之和这道题目，不仅要判断y是否存在而且还要记录y的下表位置，因为要返回x 和 y的下表。所以set 也不能用。  
此时就要选择另一种数据结构：map ，map是一种key value的存储结构，可以用key保存数值，用value在保存数值所在的下表。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_Q1NETiBASkluZ2xlczEyMw_size_21_color_FFFFFF_t_70_g_se_x_16]

class Solution {
        
    public:
        vector<int> twoSum(vector<int>& nums, int target) {
        
            vector<int> result;
            unordered_map<int,int> umap;
    
            for(int i=0;i<nums.size();i++){
        
                int rest=target-nums[i];  
    
                if(umap.count(rest)!=0){
        
                    result.push_back(umap[rest]);
                    result.push_back(i);
                    break;
                }
                else umap[nums[i]]=i;
            }
    
            return result;
    
        }
    };

[https_leetcode-cn.com_problems_two-sum]: https://leetcode-cn.com/problems/two-sum/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70]: /images/20221004/407631e372e240b28ddd204c449ae1d7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70 1]: /images/20221004/4a63c7471c7742afb562ca3ec6b69c8e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_Q1NETiBASkluZ2xlczEyMw_size_21_color_FFFFFF_t_70_g_se_x_16]: /images/20221004/d3e69ca2762a4e5b9d35330def90ee29.png