LeetCode究极刷题班

1. 两数之和
用的暴力做法——时间复杂度是O(n^2)
class Solution {public:vector twoSum(vector& nums, int target) {for(int i = 0; i < nums.size(); i++){int l = nums[i];for(int j = i + 1; j < nums.size(); j++){if(nums[j] == target - l){return {i,j};}}}return {-1,-1};}};
y总思路：
怎么实现O(n)的时间复杂度？
思路
对于给定的数组区间上，我们从头开始遍历数组，假设我们走到了箭头的位置，我们就去查看该位置前面是否有一个数等于- nums[i] ，这个查看过程我们就可以使用hash表来完成。
class Solution {public:vector twoSum(vector& nums, int target) {//声明一个hash表<数值，索引>unordered_map heap;for(int i = 0; i < nums.size(); i++){int r = target - nums[i];//查看 i 前面是否存在满足条件的数//count()是unordered_map的一个方法判断 Key 中是否存在目标值if(heap.count(r)) return {heap[r], i};//不存在则放入heap[nums[i]] = i;}return {};} };
2. 两数相加
思想
模拟了手动相加列竖式的过程，分别从两个链表头开始相加，直到两个链表结束并且没有进位。
技巧
可以创建一个虚拟头节点，方便最后结果输出
/*** 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) {//创建一个node节点， head作为虚拟头节点存放地址ListNode* head = new ListNode(0);//cur也指向第一个头节点，但是用于更新后面的节点ListNode* cur = head;int t = 0;//链表不为空，或者t不为0就一直循环while(l1 || l2 || t) {if(l1) t += l1->val, l1 = l1->next;if(l2) t += l2->val, l2 = l2->next;cur = cur->next = new ListNode(t % 10);t /= 10;}//虚拟头节点派上用处return head->next;}};
//技巧：ListNode* head = new ListNode(0);ListNode* cur = head;//等价于auto head = new ListNode(0), cur = head;
3. 无重复字符的最长子串
思路
这道题目是使用双指针算法。首先是第一个指针 i 我们枚举表示这个字串的末尾，另一个指针 j 则是从 i 开始不断往前枚举，直到最远位置。[j,i]就表示以 i 结尾的最长字串，然后枚举 i 找出所有 i 中的最长字串长度就是 res 。
为什么 i 枚举出来的就是最长字串？
假设我们 i 往后移一位， j’ 新的位置一定位于原来 j 或者 j 的右边。我们可以通过反证法说明，因为[j,i]就表示以 i 结尾的最长字串，如果 j’ 位于原来 j 的左边，说明原来的 j 不是最远的位置，就矛盾了。
所以正是这样的单调性才能得到正确的结果。并且我们通过维护一个hash表来存放[j,i]中的所有元素，当加入下一个元素的时候，如果有重复就将 j 移到重复元素的位置开始。
class Solution {public:int lengthOfLongestSubstring(string s) {unordered_map heap;int res = 0;for(int i = 0, j = 0; i < s.size(); i++){//把i字符加入到hash表中heap[s[i]]++;//判断是都存在重复，存在重复就移动j指针的位置while(heap[s[i]] > 1) heap[s[j++]]--;res = max(res, i - j + 1);}return res;}};
4. 寻找两个正序数组的中位数