题目1：1.两数之和
思路1：暴力解法
两次遍历，拿一个数和所有数相加，等于target返回下标。时间复杂度O（n2)
代码实现：
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { int n = nums.size(); for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { if (nums[i] + nums[j] == target) { return {i, j}; } } } return {}; } };
思路2：作差查找
让target-vector中的数，得到的差，然后在数组中查找。查找处可以有很多优化方式，这里提出思路（哈希查找）
代码实现：
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 {}; } };
题目2: 2.两数相加
思路1：模拟解法
两个链表，这里主要是加法，两个字符串相加或这种单个数字相加，我们要从个位开始，也就是模拟我们平时计算加法的过程。
- 从个位开始；
- 满十进一，需要一个add变量来记录是否进位；
- 当一个链表结束，另个链表补齐；
代码实现：
/** * 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) { int add = 0; ListNode *ans = new ListNode(0), *head = ans; while(l1 || l2) { int n = (l1?l1->val:0) + (l2?l2->val:0) + add; add = n/10; //判断是否进位 n %= 10; //取当前位置的值 head->next = new ListNode(n); head = head->next; (l1?l1=l1->next:0), l2?l2=l2->next:0;//很巧妙的三目运算 } if(add) head->next=new ListNode(1); return ans->next; } };
进步点分析：
- 不相连的单位数字按加法相加：add/10是进位值，add%10是当前位的值。
- 单链表结点的插入，head->next = new ListNode(n)（new+构造）
（这点不太熟悉）
LeetCode链接：2.两数相加
