力扣刷题笔记（1）两数之和（C++）

题目描述

• 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那 两个整数，并返回它们的数组下标。
• 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
• 你可以按任意顺序返回答案。

题目求解（蛮力法）

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

语法注意事项：

• C++中向量的操作：可以使用初始化列表的方式{a,b}对一个向量进行初始化；可以使用向量对象的size()方法获取向量中的元素个数。

运行时间和空间的注意事项：

• 循环终止条件：两层for循环都需要使用到数组的元素个数作为边界条件。此时，最好的做法是直接使用一个变量进行一次性获取，然后每一次循环的边界判定过程中使用，而不是每一次都重新通过size()函数获取一次，这样可以帮助减少运行时间。
• 自增运算符：一般情况下，for循环中使用前置自增运算符的速度会快于使用后置自增运算符的速度。
• if语句：为了提高程序的执行速度，可以把常见的一种情况放在if语句中，将不常见的情况放在else语句中。

题目求解（哈希表）

class Solution 
{
public:
    vector<int> twoSum(vector<int>& nums, int target) 
    {
        unordered_map<int,int> hashtable;
        int size = nums.size();
        for(int i=0;i<size;++i)
        {
            auto it = hashtable.find(target-nums[i]);
            if(it == hashtable.end())
            {
                hashtable[nums[i]] = i;
            }
            else
            {
                return {it->second,i};
            }
        }
        return {};
    }
};

语法注意事项：

• C++中的哈希表：
  • C++中使用unordered_map表示哈希表。
  • 哈希表对象创建完成后，可以使用find()方法查找哈希表中指定的元素，如果查找成功，则返回该元素的迭代器（迭代器指向一个键值对，键和值分别用迭代器的->first和->second进行获取），如果查找成功则返回哈希表的end()方法指向的尾迭代器。
  • 通过类似于Python中字典的方式，可以给C++中的哈希表构建新的元素。