排序

四数之和

还是从排序开始学习，现在来学习一个经典的问题，四数之和。同时带来一个经典的算法：排序+双指针

固定前两个数，剩下的两个数用双指针找（和为target - 前两数和）

1.将数组排序

• 相同数字挨在一起，方便去重
• 双指针可以从两端向中间移动，控制和变大变小

比如示例 1：[1,0,-1,0,-2,2]排序后 →[-2, -1, 0, 0, 1, 2]

2.两层循环固定前两个数i，j

对每个 i、j：

• 左指针 left = j + 1
• 右指针 right = len (nums) - 1

计算四数之和：total = nums[i] + nums[j] + nums[left] + nums[right]

• 如果 total < target → left 右移（让和变大）
• 如果 total > target → right 左移（让和变小）
• 如果 total == target → 记录答案，然后去重移动指针

3.用左右指针left，right找后两个数

4.跳过重复数字，避免重复答案

5.根据和的大小移动指针

我个人觉得其实套模版的东西不难，难就难在去重这个比较实际的东西。

去重的本质就是同一个位置，相同数字只处理一次。

在这道题目里面一共有四个地方需要去重：
1.第一个数i去重

#这段代码的主要目的就是确保nums[i]和前一个数不一样，而且i不是第一个数 if i > 0 and num[i] == num[i - 1]: continue

2.第二个数j去重

#j是在i后面的第二个数，如果当前nums[j]和前一个j位置的数相同，而且j不是i后面紧挨着的那个j， #那就跳过这个数 if j > i + 1 and nums[j] == nums[j - 1]: continue

3.左指针left找到答案后去重

#当在满足前提条件的情况下（left < right）,如果下一个指针和前一个指针的数值一样， #那就跳过这个指针 while left < right and nums[left] == nums[left + 1]: left += 1

4.右指针right找到答案后去重

#和右指针一样的思路，就是方向不一样 while left < right and nums[right] == nums[right - 1]: right -= 1

class Solution: def fourSum(self, nums: List[int], target: int) -> List[List[int]]: nums.sort() n = len(nums) res = []#需要有一个存放结果的容器 for i in range(n): if i > 0 and nums[i] == nums[i-1]: continue #从i的后面一位数开始，为什么没想到呢， #一定要满足不重复，所以在找j的时候需要注意这个地方 for j in range(i + 1,n): if j > i + 1 and nums[j] == nums[j-1]: continue #在刚开始的时候就要思考完善指针的位置，刚好在前两个的后面 left = j + 1 right = n - 1 #这个循环一定要有，不然后续就只能检查一次 while left < right: if nums[i] + nums[j] + nums[left] + nums[right] == target: res.append([nums[i],nums[j],nums[left],nums[right]]) #在编程思想当中，有重复值的处理方法就是跳过重复值 #排序让相同数字相邻，才让「跳过相邻重复」这个方法可行 #先把所有重复的都跳干净，再移指针进入下一轮，否则会漏跳、还会出重复解。 #保护边界，防止越界，一定要有用while，要把全部的重复值给给去掉 while left < right and nums[left] == nums[left + 1]: left += 1 while left < right and nums[right] == nums[right - 1]: right -= 1 #先不管重复，你这里本来就需要进入下一轮循环,都需要移动一次 left += 1 right -= 1 elif nums[i] + nums[j] + nums[left] + nums[right] < target: left += 1 else: right -= 1 return res

哈希表

两数之和

两数之和的问题最简单的办法其实是纯打暴力，但是有个问题就是和三数之和，四数之和不同，一定不要去重等操作，不然的话会找不到，因为题目要求返回的是下标。

不过主流的高效方法是通过哈希表来解决这个问题。

核心思想

用哈希表（字典）存储「已遍历元素：对应下标」，遍历数组时，直接查询需要的补数是否存在，用空间换时间，把 “查找” 这个动作从 O (n) 变成 O (1)。

1. 全量下标哈希

全量下标哈希的特点就是先写表，把表整体写出来之后再进行查找。

#写表 for idx in range(len(nums)): if nums[idx] in hashList.keys(): hashList[nums[idx]].append(idx) else: hashList[nums[idx]] = [idx]

• hashList 是字典
• hashList [key] 是列表，刚好对应value值就是一个列表

表的整体结构是一个字典，然后字典的value是一个列表，所以如果说没有出现过这个key值就新建一个列表[idx]，如果出现过这个key值，就在列表的后面追加其他的下标，所以这个地方可以用append()。

#查找 for key in hashList.keys(): #这是查找，可以直接找到只需要o（1） if target - key in hashList.keys()： #这里还需要遍历数组，因此整体是o（n） for idx1 in hashList[key]: #虽然说这个地方我们只需要一组解 但是我们不能直接用if，因为if是没有定义的， #我们只有使用for才可以定义idx1，进而完成下面的步骤。 for idx2 in hashList[target - key]: if idx1 != idx2: return [idx1,idx2]

1. 标准哈希

标准哈希则是边遍历边查，但是会覆盖掉重复的数字，这个就要看题目的具体要求了，不影响找到一组解。

链表

反转链表

在Python当中，我们通常通过类和节点来实现链表这种数据结构

#创建一个模版，名字叫做节点（Node） class Node: #构造一个函数其中包含两个参数，盒子self和数据value def _init_(self,value): 只要你写 self.xxx = ...，你就创造了一个叫 xxx 的属性。 self.value = value self.next = None #本例就是创建了value和next这两个属性 #属性就是变量，只是这个变量属于某个对象。

__init__不是类，它是类里面的方法

• class Node:这才是类

• def __init__(self, ...):这是类里面的一个方法（函数）

__init__特殊在哪里？创建对象时自动调用，不需要你手动写 () 去调用。

现在开始创建节点，也就是这里的Node

n1 = Node(10) n2 = Node(20) n3 = Node(30) #创建三个相互独立的节点

然后将三个节点串起来变成了一个链表

n1.next = n2 n2.next = n3 n3.next = None

现在回到反转链表这个问题，最基本的思路就是把每个节点的next箭头反过来指

所以这里就要引入一个新的方法：三指针法

• prev：前一个节点（一开始是 None）
• curr：当前节点（从头开始走）
• next_node：保存下一个节点（防止走丢）

整体的逻辑就是对于现在两个节点中间的箭头，通过遍历全部的节点来实现把全部的箭头一个一个反转

# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]: #定义最开始的两个节点，链表一直都存在，不过是通过prev和curr来标记节点 prev = None curr = head while curr: 通过这四个步骤来实现链表的反向 next_node = curr.next curr.next = prev prev = curr curr = next_node #为什么最后 return prev？ #循环结束时，curr 一定会走到 None（链表末尾） #此时 prev 正好指向原链表最后一个节点这个节点就是反转后链表的新头节点必须返回它， #外界才能拿到整条反转后的链表 return prev

贪心算法

买卖股票的最佳时机

要获取最大的利润的关键就是：对于每一个可能的卖出日，最优的买入日一定是它之前的历史最低点。最大利润，就是遍历所有卖出日，取其中最大的那一个利润。

遍历每一天作为卖出日，每一天都用它前面的最优买入价（最低价）计算利润，最后取最大的那个

class Solution: def maxProfit(self, prices: List[int]) -> int: max_prof = 0 min_price = prices[0] if len(prices) < 2: return 0 for price in prices[1:]: min_price = min(min_price,price) curr_prof = price - min_price max_prof = max(max_prof, curr_prof) return max_prof

1. 为什么只存一个最低价不会漏最优解？

存储的是阶段性最低价，而非固定全局最低价。前期算出的最大利润会永久保留，后续更低价格只会影响后面的卖出日，不会覆盖之前的最优解。

2. 持续下跌为什么不会返回负数？

max_profit初始为0，每次对比max(0, 负数)，自动放弃亏损交易，保底返回0。

3. 为什么是贪心算法？

每一步只保留局部最优（当前最低价、当前最大利润），不回溯、不枚举、不预判未来，最终累加得到全局最优解。

滑动窗口

无重复字符的最长字串

在这里先介绍两个概念：子串和子序列

子串：必须是原字符串中连续的一段字符
子序列：不要求字符连续，只要求字符的先后顺序不变

原字符串：abcde 子串：abc bcd cde 子序列：ace abd bde

本题要求是子串，那么就一定要连续

最直接的思路是：

1. 枚举字符串中的所有子串。

2. 检查每个子串中是否存在重复字符。

3. 记录所有合法子串中的最大长度。

显然这样的效率非常低

因此这里引入滑动窗口的算法思想

滑动窗口需要用到两个指针

left right

两个指针共同表示数组或字符串的一个连续区间

在代码中，这个窗口通常表示为：

s[left:right + 1]

滑动窗口的基本思想是：

right 向右移动，扩大窗口。 left 向右移动，缩小窗口。

可以把它想象成一个可以伸缩的框：

[a] [ab] [abc] [bca] [cab]

右边界负责不断加入新的字符。

如果加入新字符后不满足题目条件，左边界就向右移动，直到窗口重新满足条件。

在本题中：

right不断向右移动，尝试扩大窗口
如果出现重复的字符，就移动左窗口来缩小窗口
窗口重新没有重复字符后，记录它的长度

最核心的地方就是要始终保证当前窗口没有重复字符。

还两点需要补充的是：
我们可以使用一个集合window，记录当前窗口中已经存在的字符。因为这样就不会有重复。
在滑动窗口的时候需要删除集合中的元素，通过remove函数：window.remove(s[left])

class Solution: def lengthOfLongestSubstring(self, s: str) -> int: window = set() max_length = 0 left = 0 for right in range(len(s)): while s[right] in window: window.remove(s[left]) left += 1 window.add(s[right]) max_length = max(max_length,len(window)) #本题是刚好可以用len(window)，更为通用的方法是right - left + 1 return max_length