排序四数之和还是从排序开始学习现在来学习一个经典的问题四数之和。同时带来一个经典的算法排序双指针固定前两个数剩下的两个数用双指针找和为target - 前两数和1.将数组排序相同数字挨在一起方便去重双指针可以从两端向中间移动控制和变大变小比如示例 1[1,0,-1,0,-2,2]排序后 →[-2, -1, 0, 0, 1, 2]2.两层循环固定前两个数ij对每个 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.用左右指针leftright找后两个数4.跳过重复数字避免重复答案5.根据和的大小移动指针我个人觉得其实套模版的东西不难难就难在去重这个比较实际的东西。去重的本质就是同一个位置相同数字只处理一次。在这道题目里面一共有四个地方需要去重1.第一个数i去重#这段代码的主要目的就是确保nums[i]和前一个数不一样而且i不是第一个数 if i 0 and num[i] num[i - 1]: continue2.第二个数j去重#j是在i后面的第二个数如果当前nums[j]和前一个j位置的数相同而且j不是i后面紧挨着的那个j #那就跳过这个数 if j i 1 and nums[j] nums[j - 1]: continue3.左指针left找到答案后去重#当在满足前提条件的情况下left right,如果下一个指针和前一个指针的数值一样 #那就跳过这个指针 while left right and nums[left] nums[left 1]: left 14.右指针right找到答案后去重#和右指针一样的思路就是方向不一样 while left right and nums[right] nums[right - 1]: right - 1class 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)。全量下标哈希全量下标哈希的特点就是先写表把表整体写出来之后再进行查找。#写表 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(): #这是查找可以直接找到只需要o1 if target - key in hashList.keys() #这里还需要遍历数组因此整体是on for idx1 in hashList[key]: #虽然说这个地方我们只需要一组解 但是我们不能直接用if因为if是没有定义的 #我们只有使用for才可以定义idx1进而完成下面的步骤。 for idx2 in hashList[target - key]: if idx1 ! idx2: return [idx1,idx2]标准哈希标准哈希则是边遍历边查但是会覆盖掉重复的数字这个就要看题目的具体要求了不影响找到一组解。链表反转链表在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__特殊在哪里创建对象时自动调用不需要你手动写 () 去调用。现在开始创建节点也就是这里的Noden1 Node(10) n2 Node(20) n3 Node(30) #创建三个相互独立的节点然后将三个节点串起来变成了一个链表n1.next n2 n2.next n3 n3.next None现在回到反转链表这个问题最基本的思路就是把每个节点的next箭头反过来指所以这里就要引入一个新的方法三指针法prev前一个节点一开始是 Nonecurr当前节点从头开始走next_node保存下一个节点防止走丢整体的逻辑就是对于现在两个节点中间的箭头通过遍历全部的节点来实现把全部的箭头一个一个反转# Definition for singly-linked list. # class ListNode: # def __init__(self, val0, nextNone): # 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_prof1. 为什么只存一个最低价不会漏最优解存储的是阶段性最低价而非固定全局最低价。前期算出的最大利润会永久保留后续更低价格只会影响后面的卖出日不会覆盖之前的最优解。2. 持续下跌为什么不会返回负数max_profit初始为0每次对比max(0, 负数)自动放弃亏损交易保底返回0。3. 为什么是贪心算法每一步只保留局部最优当前最低价、当前最大利润不回溯、不枚举、不预判未来最终累加得到全局最优解。滑动窗口无重复字符的最长字串在这里先介绍两个概念子串和子序列子串必须是原字符串中连续的一段字符子序列不要求字符连续只要求字符的先后顺序不变原字符串abcde 子串abc bcd cde 子序列ace abd bde本题要求是子串那么就一定要连续最直接的思路是枚举字符串中的所有子串。检查每个子串中是否存在重复字符。记录所有合法子串中的最大长度。显然这样的效率非常低因此这里引入滑动窗口的算法思想滑动窗口需要用到两个指针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
