LeetCode_刷题学习

1.两数之和

1.1题目

1.2练习记录

1.2.1思路

1.两个for循环遍历太慢了，尝试使用for循环和find函数来实现。
2.由于vector的find函数返回的是迭代器，通过和nums.end()对比来判断是否找到；
3.find函数会找到第一个for循环中选定的值，这会导致下标重复，所以还需要多加一个判断排除自身元素。
4.为了更方便的判断，所以将for循环中的int i改为了iterator遍历。
5.这样就很方便的找到两个对应数字所在的iterator位置。
6.用STL中的distance函数完成iterator到下标的转换。

1.2.2代码及结果

class Solution {
public:
   vector<int> twoSum(vector<int>& nums, int target) {
       vector<int> vecNum;
       for(vector<int>::iterator i=nums.begin();i != nums.end();++i)
       {
           vector<int>::iterator findIndex=std::find(nums.begin(),nums.end(),target-(*i));
           if(nums.end() != findIndex
           && i != findIndex)
           {
               //vector<int> vecNum;
               vecNum.push_back(distance(nums.begin(),i));
               vecNum.push_back(distance(nums.begin(),findIndex));
               //return vecNum;
               break;
           }
       }
       return vecNum;
   }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

1.3标答及知识点

13.1标答

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 {};
    }
};

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/two-sum/solution/liang-shu-zhi-he-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

1.3.2知识点

• unordered_map为 无序map 类型
• map中first存的 值，second存的下标，所以最后return的都是下标，命名上最好为Value2Index
• 巧妙的利用了第一次for循环不可能找到对应解来进行赋值