无重复字符的最长子串

https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/

思路：滑动窗口

暴力解法：两次遍历，记录以每一个字符开头的最长无重复字符子串，返回最大值，时间复杂度O(n^2^)

肯定会超时

观察可以发现一个规律：假设 Si-j 是以第 i 个字符开头的无重复字符最长子串，那么当以第 i+1 个字符开头时，i+1到 j 一定也是无重复字符子串，右指针不用回退，也就是说可以维护一个滑动窗口。时间复杂度O(n)。

反转链表

https://leetcode.cn/problems/reverse-linked-list/

思路：mock_head = nullptr ，p指针指向head，q指针指向mock_head，也就是说p指针在右，q指针在左，当p非空时，循环执行：先记录p的下一个节点到tmp，把p->next指向q，然后把q放到p的位置，最后把p放到tmp。

数组中第K个最大元素

https://leetcode.cn/problems/kth-largest-element-in-an-array/description/

思路：维护一个大小为K的最小堆，堆中的元素是数组中最大的K个，堆顶的元素就是答案

1
priority_queue<int, vector<int>, greater<int>> min_heap;

三数之和

https://leetcode.cn/problems/3sum/

暴力解法：三重循环，时间复杂度O(n^3^)。

三指针解法：先把数组排序，定义三个指针，i，j = i + 1，k = nums.size() - 1

i 由外层 for 循环控制，去重机制：if(i > 0 && nums[i] == nums[i - 1]) continue;

内层由一个 while 语句控制 j 和 k ，while (j < k)

计算当前的三数之和：

（1）如果为0，那么保存结果，更新 j 和 k 的值，注意：更新时 j 和 k 都要考虑去重：

1
2
3
4
while (j < k && nums[j] == nums[j + 1]) ++j;
while (j < k && nums[k] == nums[k - 1]) --k;
++j;
--k;

（2）如果和大于0，–k

（3）否则，++j

最大子数组和

https://leetcode.cn/problems/maximum-subarray/

思路：考虑以第 i 个位置结束的子数组，nums[i] 有两种选择：要么和前面构成数组，要么自己单独成一个数组

所以这道题可以考虑动态规划，dp[i]记录以 nums[i] 结尾的最大连续子数组，dp[i + 1] = max(dp[i] + nums[i + 1]， nums[i + 1])

1
2
3
4
5
6
7
8
9
int m = nums.size();
vector<int> dp(m, 0);
dp[0] = nums[0];
int res = dp[0];
for (int i = 1; i < m; ++i) {
    dp[i] = max(dp[i - 1] + nums[i], nums[i]);
    res = max(res, dp[i]);
}
return res;

最长回文子串

https://leetcode.cn/problems/longest-palindromic-substring/

思路：遍历字符串中的每一个字符，计算以该字符为中心的最长回文子串，这时分两种情况：奇数扩散和偶数扩散，取两者最大值，遍历过程中记录最大回文子串的长度和该子串的中心位置dex，计算出子串的左端点，最后使用：

1
s.substr(left, max_len)

合并两个有序链表

https://leetcode.cn/problems/merge-two-sorted-lists/description/

思路：使用三个指针，p、q 和 cur ，前俩分别指向这两个链表的头节点，new一个mock_head节点，cur指向它，最后返回mock_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
ListNode* p = list1;
ListNode* q = list2;
ListNode* mock_head = new ListNode(0);
ListNode* cur - mock_head;

while (p != nullptr || q != nullptr) {
    if (p == nullptr) {
        cur->next = q;
        break;
    }
    if (q == nullptr) {
        cur->next = p;
        break;
    }
    if (p->val < q->val) {
        cur->next = p;
        cur = p;
        p = p->next;
    } else {
        cur->next = q;
        cur = q;
        q = q->next;
    }
}

return mock_head->next;