sliding window方法
3. 无重复字符的最长子串
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
if not s:return 0
left = 0
lookup = set()
n = len(s)
max_len = 0
cur_len = 0
for i in range(n):
cur_len += 1
while s[i] in lookup:
lookup.remove(s[left])
left += 1
cur_len -= 1
if cur_len > max_len:max_len = cur_len
lookup.add(s[i])
return max_len
双指针滑动窗口解法，时间复杂度O(N)
209. 长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组，返回 0。
示例:
输入: s = 7, nums = [2,3,1,2,4,3]
输出: 2
解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。
进阶:
如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法
滑动窗口，想象一下，在一个坐标上存在两个指针begin 和i ，begin 代表滑窗的左边框，i代表滑窗的右边框。两者通过分别向右滑动，前者能使窗口之间的和减小，后者能使窗口之间的和增大。开始时二者重合，窗口的和就是重合点所在的数。
开始i向右滑动，使和变大。
当恰好大于等于s时，记录滑窗所包括的子数组长度ans，若ans已有数值，需判断新值是否小于旧值，若是，更新ans。begin向右滑动
判断是否仍大于等于s
若是，重复步骤2，3。若否，转步骤1。直到右边框到达最右边
class Solution:
def minSubArrayLen(self, s: int, nums: List[int]) -> int:
if nums==[]:
return 0
l,r,sum,min_len=0,0,0,float('inf')
while r<len(nums):
sum += nums[r]
r += 1
while sum >= s:
min_len = min(min_len,r-l)
sum-=nums[l]
l+=1
if min_len==float('inf'):
return 0
return min_len
双指针的意义在于将原来的二重循环变为两个指针从头尾一起遍历，时间复杂度O(n)
15. 三数之和
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
if len(nums)<3:
return []
ans,target = [], 0
nums.sort()
for i in range(len(nums)-2):
if i>0 and nums[i]==nums[i-1]:
continue
l, r = i+1, len(nums)-1
while l<r:
total = nums[i]+nums[l]+nums[r]
if total>target:
r-=1
elif total<target:
l+=1
else:
ans.append([nums[i],nums[l],nums[r]])
while l<r and nums[l]==nums[l+1]:
l+=1
while l<r and nums[r]==nums[r-1]:
r-=1
l+=1
r-=1
return ans
16. 最接近的三数之和
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.
与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).
不懂为什么这里的代码不用判断重复，而且加了[while nums[r]==nums[r+1]:
r++]反而输出错误，而15题可以判断重复，哭哭！！
def threeSumClosest(self, nums, target):
nums.sort()
res = sum(nums[:3])
for i in range(len(nums)-2):
l, r = i+1, len(nums)-1
while l < r:
s = sum((nums[i], nums[l], nums[r]))
if abs(s-target) < abs(res-target):
res = s
if s < target:
l += 1
elif s > target:
r -= 1
else: # break early
return res
return res
18. 四数之和
给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：
答案中不可以包含重复的四元组。
示例：
给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
满足要求的四元组集合为：
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
方法A
用二层循环加双指针，时间复杂度O(n3),运行速度最快。原因主要是设置了过滤条件，否则就是暴力法。我自己写的没有加xx4<target xx*3<target-nums[i]这样的过滤条件，就运行超级慢
参考下，可移植性不强
class Solution:
def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
if not nums:
return []
_4_sum_list = []
nums.sort()
if nums[-1]*4 < target:
return []
for i in range(len(nums)-3):
if nums[i]*4 > target:
break
if i==0 or nums[i]!= nums[i-1]:
ele = nums[i]
target_3_sum = target - ele
if nums[-1]*3 < target_3_sum:
continue
for j in range(i+1,len(nums)-2):
ele2 = nums[j]
if ele2*3 > target_3_sum:
break
if j==i+1 or ele2!= nums[j-1]:
target_2_sum = target_3_sum - ele2
point_left = j+1
point_right = len(nums)-1
while point_left < point_right:
if nums[point_left] + nums[point_right] > target_2_sum:
point_right -= 1
elif nums[point_left] + nums[point_right] < target_2_sum:
point_left += 1
else:
aaa = [ele, ele2,nums[point_left], nums[point_right]]
_4_sum_list.append(aaa)
point_left += 1
point_right -= 1
while point_left < point_right and nums[point_left] == nums[point_left-1]:
point_left += 1
while point_left < point_right and nums[point_right] == nums[point_right+1]:
point_right -= 1
return _4_sum_list
方法B
字典查找法
总思路：把N4拆成2个N2。第一个for循环，先求后2个值可能的取值的所有情况，并且把它们储存在一个字典里，以和作为键。
第二个for，我们遍历前2个值所可能取的各种值，算出和并且检查target - onesum是否在我们的字典里，如果在，就说明我们找到了一个解。其实这种求几数之和的问题，都可以通过这种思路。比如说三数之和，现在我就想到根本不必用指针，算出所有后2个值所加的可能的和，然后用字典存，最后用target-第一个值去检查是否存在这样的键。
class Solution:
def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
nums.sort()
ans = set()
sumans = {}
if len(nums) < 4:
return []
for i in range(2, len(nums) - 1):
for j in range(i+1, len(nums)):
onesum = nums[i] + nums[j]
if onesum not in sumans:
sumans[onesum] = [(i, j)]
else:
sumans[onesum].append((i, j))
for i in range(len(nums) - 3):
for j in range(i+1, len(nums) - 2):
onesum = nums[i] + nums[j]
if target - onesum in sumans:
for k in sumans[target - onesum]:
if k[0] > j:
ans.add((nums[i], nums[j], nums[k[0]], nums[k[1]]))
return [i for i in ans]
小trick:
collections 这个库
from collections import defaultdict
dict = defaultdict(int)
给字典中的Key一个默认值，放入int的话默认值是0
collections.Counter()函数
用来计算列表中元素出现次数，存入字典
import collections
count = collections.Counter(a)
count
Counter({5: 4, 1: 1, 2: 1, 3: 1, 4: 1})
