哈希与双指针

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) 时间复杂度的解法

image.png

滑动窗口，想象一下，在一个坐标上存在两个指针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})