Leetcode---2021/7/27

浅浅的花香味﹌ 2022-09-01 00:58 87阅读 0赞

### 目录 ###

*  存在重复元素
 *  最大子序和
 *  两数之和
 *  合并两个有序数组
 *  两个数组的交集 II
 *  买卖股票的最佳时机

# 存在重复元素 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70]  
分析：  
  哈希表。  
代码：

class Solution { 
    public:
        bool containsDuplicate(vector<int>& nums) { 
            map<int, int> mp;
            for(int x : nums) { 
                mp[x]++;
                if(mp[x] > 1) { 
                    return true;
                }
            }
            return false;
        }
    };

# 最大子序和 #

[剑指 Offer 42. 连续子数组的最大和][Offer 42.]

# 两数之和 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 1]  
方法一：  
  暴力求解。  
代码：

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

方法二：  
  一次遍历，每次首先查找target - nums\[i\]是否在哈希表中，是就返回当前值和target - nums\[i\]；否则将当前值存入哈希表。  
代码：

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]);
                if (it != hashtable.end()) { 
                    return { it->second, i};
                }
                hashtable[nums[i]] = i;
            }
            return { };
        }
    };

# 合并两个有序数组 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 2]  
分析：  
  简单的双指针。  
代码：

class Solution { 
    public:
        void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { 
            int ind1 = 0, ind2 = 0, ind = 0;
            vector<int> res(m + n);
            while(ind1 < m && ind2 < n) { 
                if(nums1[ind1] <= nums2[ind2]) { 
                    res[ind] = nums1[ind1];
                    ind1++;
                }else { 
                    res[ind] = nums2[ind2];
                    ind2++;
                }
                ind++;
            }
            if(ind1 == m) { 
                for(int i = ind2; i < n; i++) { 
                    res[ind++] = nums2[i];
                }
            }else { 
                for(int i = ind1; i < m; i++) { 
                    res[ind++] = nums1[i];
                }
            }
            for(int i = 0; i < m + n; i++) { 
                nums1[i] = res[i];
            }
        }
    };

# 两个数组的交集 II #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 3]

class Solution { 
    public:
        vector<int> intersect(vector<int>& nums1, vector<int>& nums2) { 
            sort(nums1.begin(), nums1.end());
            sort(nums2.begin(), nums2.end());
            int m = nums1.size(), n = nums2.size();
            int ind1 = 0, ind2 = 0;
            vector<int> res;
            while(ind1 < m && ind2 < n) { 
                if(nums1[ind1] == nums2[ind2]) { 
                    res.push_back(nums1[ind1]);
                    ind1++, ind2++;
                }else if(nums1[ind1] < nums2[ind2]) { 
                    ind1++;
                }else { 
                    ind2++;
                }
            }
            return res;
        }
    };

class Solution { 
    public:
        vector<int> intersect(vector<int>& nums1, vector<int>& nums2) { 
            unordered_map<int, int> mp;
            vector<int> res;
            for(int x : nums1) { 
                mp[x]++;
            }
            for(int x : nums2) { 
                if(mp.find(x) != mp.end() && mp[x] > 0) { 
                    res.push_back(x);
                    mp[x]--;
                }
            }
            return res;
        }
    };

# 买卖股票的最佳时机 #

[剑指 Offer 63. 股票的最大利润][Offer 63.]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70]: /images/20220829/008950b62335461abccd1885b2a5e4e3.png
[Offer 42.]: https://blog.csdn.net/Cyril_KI/article/details/118863971
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 1]: /images/20220829/b2447cc85dbb47778f50da29fd6f2707.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 2]: /images/20220829/c535ca551ffc4fcbbecf2cadeaaa66dd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 3]: /images/20220829/fb9bc6e23df64a7dbbd70a07a6397898.png
[Offer 63.]: https://blog.csdn.net/Cyril_KI/article/details/119028893