LeetCode第1题-两数之和（C++实现）_class solution <%public:vector twosum(vector<

大家好，我是一只学弱狗，记录学习的点点滴滴！
算法才是程序设计的灵魂，每日一题！

优质文章

• 一张黄图的故事
• JavaSE练习项目
• 我是菜鸟、我小试牛刀
• linux指令太多记不住？小白看这篇就够了！

优质专栏

• 数据库就该这样学
• 爪哇外步篇

---

第一想法，就是暴力枚举

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> result(2);
         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 {};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

第二种做法，网上看的，查找表法

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int,int> recode;
        for(int i=0;i<nums.size();i++){
            if(recode.find(target-nums[i]) == recode.end()){
                recode[nums[i]]=i;
            }else{
                return {recode[target-nums[i]],i};
            }
        }
         return {};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

因为是第一次刷LeetCode的题目，有些规则还是不太懂的，搞了挺长时间的。。
以后没做一个题，我都会写一些感想与经验，但是每篇均不会重复

规则此题：我再次熟悉了vector和map的使用

对于vector，它更像java中的ArrayList，如果是函数返回值的时候，可以直接写{1,2}
对于map来说，就比好重要了，有普通的map，也有unordered_map，但是devcpp好像不支持，，，，解决方法如何在Dev-Cpp中使用C++11中的函数
然后就是一些编程习惯，比如若常常使用多次同一个值，像双层for循环使用数组的长度，可以用一个变量来保存，当然，这也是看大佬学到的，

最后就是用查找表法解决这个题，也是我没想到的。。

map的底层实现时红黑树
而unordered_map的底层实现时哈希，如果不考虑排序的话，用unordered_map更快一些

附上最好的代码

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> rec;
        for(int i=0;i<nums.size();i++){
            if(rec.find(target-nums[i])==rec.end()){
                rec[nums[i]]=i;
            }else{
                return {rec[target-nums[i]],i};
            }
        }
        return {};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

看了解析，这种能写更少的代码，大家参考下就行，思路一样的

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* head = new ListNode;
	ListNode* front = head;
	int jinwei = 0; 
    while(l1!=NULL && l2!=NULL){
    	int sum = l1->val + l2->val + jinwei;
    	ListNode* tmp = new ListNode(sum%10);
    	jinwei = sum/10;
    	front->next = tmp;
    	front = tmp;
    	l1 = l1->next;
    	l2 = l2->next;
	}
	while(l1!=NULL){
		int sum = l1->val + jinwei;
		ListNode* tmp = new ListNode(sum%10);
		jinwei = sum/10;
		front->next = tmp;
		front = tmp;
		l1 = l1->next;
	}
	while(l2!=NULL){
		int sum = l2->val + jinwei;
		ListNode* tmp = new ListNode(sum%10);
		jinwei = sum/10;
		front->next = tmp;
		front = tmp;
		l2 = l2->next;
	}
	if(jinwei!=0){
		ListNode* tmp = new ListNode(jinwei);
		front->next = tmp;
	}
    return head->next;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

但是还没上面的那个执行的快。。。