[Leetcode]数据结构之数组——python版本

[Leetcode]数据结构之数组——python版本

本篇文章根据labuladong的算法小抄汇总数组的常见算法，采用python3实现

文章目录

前缀和技巧

一维数组中的前缀和

区域和检索——数组不可变，T303 二维数组中的前缀和

二维区域和检索——矩阵不可变，T304 和为k的子数组，T560 差分数组技巧

区间加法，T370航班预定统计，T1109拼车，T1094 双指针技巧总结

快慢指针

判定链表中是否有环，T141返回链表中环的起始位置，T142寻找链表中点，T876寻找链表的倒数第n个结点，T19 左右指针

二分查找两数之和Ⅱ，T167反转数组，T344 滑动窗口算法

最小覆盖字串，T76字符串的排列，T567找到字符串中所有字母异位词，T438无重复字符的最长子串，T3 基本二分搜索

二分查找框架二分查找，T704寻找左侧边界的二分搜索寻找右侧边界的二分查找在排序数组中查找元素的第一个和最后一个位置，T34 二分搜索的应用

爱吃香蕉的珂珂，T875在D天内送达包裹的能力，T1011分割数组的最大值，T410 田忌赛马——优势洗牌，T870常数时间删除/查找数组中任意元素

常数时间插入、删除和获取随机元素，T380 TWOSUM问题

TWOSUM Ⅰ，T1TwoSum Ⅱ，T170数组去重问题去除重复字母，T316 原地修改数组

有序数组去重，T26有序链表去重，T83移除元素，T27移动零，T283

前缀和技巧

特点：原始数组不会被修改的情况下，快速、频繁地计算一个索引区间内的元素之和

一维数组中的前缀和 区域和检索——数组不可变，T303

题目：给定一个整数数组nums，求数组从索引i到j范围内元素的总和，包括i和j

class NumArray:
    def __init__(self,nums):
        self.nums = nums
        #从1开始
        self.preSum = [0 for i in range(len(nums)+1)]
        for i in range(1,len(nums)+1):
            self.preSum[i] = self.preSum[i-1] + nums[i-1]
    
    def sumRange(self,left,right):
        return self.preSum[right+1] - self.preSum[left]

二维数组中的前缀和 二维区域和检索——矩阵不可变，T304

class NumMatrix:
    def __init__(self,matrix):
        self.matrix = matrix
        m = len(matrix)
        n = len(matrix[0])
        if m == 0 or n == 0:
            return
        self.preSum = [[0 for i in range(n+1)] for j in range(m+1)]
        for i in range(1,m+1):
            for j in range(1,n+1):
                self.preSum[i][j] = self.preSum[i-1][j] + self.preSum[i][j-1] + matrix[i-1][j-1] - self.preSum[i-1][j-1]
        
    #返回左上角(row1,col1)到右下角(row2,col2)的子矩阵元素总和
    def sumRegion(row1,col1,row2,col2):
        return self.preSum[row2+1][col2+1] + self.preSum[row1][col1] - self.preSum[row1][col2+1] - self.preSum[row2+1][col1]

和为k的子数组，T560

题目：给定一个整数数组nums和整数k，统计并返回该数组中和为k的连续子数组的个数

def subarraySum(nums,k):
    n = len(nums)
    #前缀和：其出现的次数
    preSum = dict()
    preSum[0] = 1
    res = 0
    sum0_i = 0
    for i in range(n):
        sum0_i += nums[i]
        sum0_j = sum0_i - k
        if sum0_j in preSum:
            res += preSum[sum0_j]
        if sum0_i in preSum:
            preSum[sum0_i] += 1
        else:
            preSum[sum0_i] = 1
    return res

差分数组技巧

特点：适用于频繁对原始数组的某个区间的元素进行增减

方法：先对nums构造一个diff差分数组，diff[i]就是nums[i]和nums[i-1]之差

#根据nums推出diff
n = len(nums)
diff = [0 for i in range(n)]
diff[0] = nums[0]
for i in range(1,n):
    diff[i] = nums[i] - nums[i-1]
    
#根据diff反推nums
n = len[diff]
res = [0 for i in range(n)]
res[0] = diff[0]
for i in range(1,n):
    res[i] = res[i-1] + diff[i]

通过差分数组diff，可以快速进行区间增减。

如果想对区间nums[i…j]的元素全部加3，那么只需要让diff[i]+=3；diff[j+1] -= 3。

只要花费O(1)时间修改diff数组，就相当于给nums整个区间做了修改。多次修改diff，然后通过diff反推nums即可获得nums修改后的结果。

把差分数组抽象成类：

class Difference:
    def __init__(self,nums):
        self.nums = nums
        n = len(nums)
        if n == 0:
            return
        self.diff = [0 for i in range(n)]
        self.diff[0] = nums[0]
        for i in range(1,n):
            diff[i] = nums[i] - nums[i-1]
    #给闭区间[i,j]增加val
    def increment(self,i,j,val):
        self.diff[i] += val
        if j < len(self.diff) - 1:
            self.diff[j+1] -= val
    #返回结果数组
    def result(self):
        res = [0 for i in range(len(self.diff))]
        res[0] = diff[0]
        for i in range(1,len(self.diff)):
            res[i] = res[i-1] + self.diff[i]
        return res

区间加法，T370

题目：有一长度为n的数组，初始情况下所有数字为0。将会被给出k个更新的 *** 作。其中，每个 *** 作会被表示成三元组[startIndex,endIndex,inc]，意思是将子数组A[startIndex…endIndex]增加inc。请你返回k次 *** 作后的数组。

def getModifiedArray(length,updates):
    diff = [0 for i in range(length)]
    for i,j,val in updates:
        diff[i] += val
        if j < length - 1:
            diff[j] -= val
    res = [0 for i in range(length)]
    res[0] = diff[0]
    for i in range(1,n):
        res[i] = res[i-1] + diff[i]
    return res

航班预定统计，T1109

题目：有1…n的n个航班。有航班预定表，第i条预定记录bookings[i]=[i,j,k]意味着从i到j的每个航班上预定了k个座位。要求返回长度为n的数组answer，按航班编号顺序返回每个航班上预定的座位数。

class Solution:
    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
        #diff[i]表示第i+1个航班和第i个航班的差距
        diff = [0 for i in range(n)]
        for i,j,seat in bookings:
            diff[i-1] += seat
            if j < n:
                diff[j] -= seat
        res = [0 for i in range(n)]
        res[0] = diff[0]
        for i in range(1,n):
            res[i] = res[i-1] + diff[i]
        return res

拼车，T1094

题目：假设你是顺风车司机，车上最初有capacity个空座位可用于载客。车不允许掉头或改变方向，只能向一个方向行驶。有一份乘客计划表trips，trips[i]=[num_passengers,start_location,end_location]包含了第i组乘客的形成信息，分别是乘客数量，上车地点，下车地点。地点未知是从初始出发位置行驶到这些地点所需的距离。请判断你的车是否可以顺利完成接送所有乘客的任务。

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:

        diff = [0 for i in range(1001)]
        for num,start,end in trips:
            if num > capacity:
                return False
            diff[start] += num
            if end < 1000:
                diff[end] -= num
        
        res = [0 for i in range(1001)]
        res[0] = diff[0]
        for i in range(1,1001):
            res[i] = res[i-1] + diff[i]
            if res[i] > capacity:
                return False
        return True

双指针技巧总结 快慢指针

特点：快慢指针主要解决链表中的问题，比如判定链表中是否包含环

判定链表中是否有环，T141

def hasCycle(head):
    fast = head
    slow = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if fast == slow:
            return True
    return False

返回链表中环的起始位置，T142

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        slow = head
        fast = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                slow = head
                while slow != fast:
                    slow = slow.next
                    fast = fast.next
                break
        if (not fast) or (not fast.next):
            return None
        else:
            return slow

寻找链表中点，T876

def middleNode(head):
    fast = head
    slow = head
    while fast and fast.next:
        fast = fast.next.next
        slow = slow.next
    return slow

寻找链表中点的一个重要作用是对链表进行归并排序。

数组的归并排序是求中点索引递归地把数组二分，最后合并两个有序数组。

寻找链表的倒数第n个结点，T19

def removeNthFromEnd(head,n):
    p = ListNode(-1)
    p.next = head
    slow = p
    fast = p
    for i in range(n):
        fast = fast.next
   	while fast and fast.next:
        fast = fast.next
        slow = slow.next
    slow.next = slow.next.next
    return p.next

左右指针

特点：左右指针主要解决数组或字符串中的问题，比如二分查找

左右指针在数组中指的是两个索引值，一般初始化为left = 0,right = len(nums) - 1

只要数组有序，就应该想到双指针技巧。

二分查找

def binarySearch(nums,target):
    left = 0
    right = len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

两数之和Ⅱ，T167

题目：给定一个按照非递减顺序排列的整数数组numbers（从1开始计数），请你从数组中找出两个数满足相加之和等于目标数target。要求返回这两个数的下标值。假设只有唯一答案，不能重复使用相同元素。

def twoSum(nums,target):
    left = 0
    right = len(nums) - 1
    while left < right:
        sum = nums[left] + nums[right]
        if sum == target:
            return [left+1,right+1]
        elif sum < target:
            left += 1
        else:
            right -= 1
    return [-1,-1]

反转数组，T344

必须原地修改输入的字符数组，额外空间为O(1)

def reverseString(s):
    left = 0
    right = len(s) - 1
    while left < right:
        s[left],s[right] = s[right],s[left]
        left += 1
        right -= 1

滑动窗口算法

滑动窗口可以解决一大类子字符串匹配的问题。

框架：

def slidingWindow(s,t):
    need = dict()
    window = dict()
    for c in t:
        need[c] += 1
	left = 0
    right = 0
    valid = 0
    while right < len(s):
        #c是即将移入窗口的字符
        c = s[right]
        #右移窗口
        right += 1
        #进行窗口内数据的一系列更新
        ......
        #debug输出
       	print("window:[{},{}]n".format(left,right))
        #判断左侧窗口是否要收缩  
        while (窗口需要缩小):
            #d是要移除窗口的字符
            d = s[left]
            #调整窗口
            left += 1
            #进行窗口内数据的一系列更新
            ......

时间复杂度为O(N)

最小覆盖字串，T76

题目：在字符串S中找出包含字符串T中所有字母的最短子串

方法：

初始化left=right=0。[left,right)为一个窗口先不断增加right扩大窗口，直到窗口中字符串符合要求停止增加right，转而增加left缩小窗口，直到窗口中的字符串不再符合要求。每增加left都要更新一轮结果。重复step2和step3，直到right到达字符串s的尽头。

needs：记录T中字符出现的次数

window：记录窗口中相应字符出现的次数

def minWindow(s,t):
    need = dict()
    window = dict()
    #初始化need
    for c in t:
        if c in need:
            dict[c] += 1
        else:
            dict[c] = 1
    left = 0
    right = 0
    valid = 0 #窗口中满足need条件的字符个数，如果valid==len(need)说明窗口满足条件
    #记录最小覆盖字串的起始索引和长度
    start = 0
    n = len(s)
    leng = n + 1
    while right < n:
        #c是将移入窗口的字符
        c = s[right]
        right += 1
        if c in need:
            if c in window:
                window[c] += 1
            else:
                window[c] = 1
            if window[c] == need[c]:
                valid += 1
        #判断左侧窗口是否收缩
        while valid == len(need):
            if right - left < leng:
                start = left
                leng = right - left
            #d是即将移除窗口的字符
            d = s[left]
            left += 1
            if d in need:
                if window[d] == need[d]:
                    valid -= 1
                window[d] -= 1
    return "" if leng == n + 1 else s[start:start+leng]

字符串的排列，T567

判断字符串s2是否包含字符串s1的排列，即s1的排列之一是s2的子串

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        need = dict()
        for c in s1:
            if c in need:
                need[c] += 1
            else:
                need[c] = 1
        window = dict()
        left = 0
        right = 0
        n = len(s2)
        valid = 0
        while right < n:
            c = s2[right]
            right += 1
            if c in need:
                if c in window:
                    window[c] += 1
                else:
                    window[c] = 1
                if window[c] == need[c]:
                    valid += 1
                    if valid == len(need):
                        return True
                elif window[c] > need[c]:
                    d = s2[left]
                    left += 1
                    if d in window:
                        if window[d] == need[d]:
                            valid -= 1
                        window[d] -= 1                   
            else:
                left = right
                window = dict()
                valid = 0

        return False

找到字符串中所有字母异位词，T438

题目：找到字符串s中所有字符串p的异位词的子串，返回子串的起始索引。异位词是指相同字母重排列形成的字符串（包括相同字符串）

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        need = dict()
        window = dict()
        for c in p:
            if c in need:
                need[c] += 1
            else:
                need[c] = 1
        left = 0
        right = 0
        n = len(s)
        valid = 0
        res = []
        while right < n:
            c = s[right]
            right += 1
            if c in need:
                if c in window:
                    window[c] += 1
                else:
                    window[c] = 1
                if window[c] == need[c]:
                    valid += 1
                    if valid == len(need):
                        res.append(left)
                        #已完成一个匹配，准备进行下一次匹配
                        d = s[left]
                        left += 1
                        #由于本来是完全匹配的，这里删一个肯定少一个有效的
                        valid -= 1
                        window[d] -= 1  
                #本来c刚好匹配，现在c多了一个，那么就要从左边往右删                      
                elif window[c] > need[c]:
                    valid -= 1
                    d = s[left]
                    while d != c:
                        if window[d] == need[d]:
                            valid -= 1
                        left += 1
                        window[d] -= 1
                        d = s[left]
                    else:
                        valid += 1
                        left += 1
                        window[d] -= 1
            else:
                left = right
                window = dict()
                valid = 0
        return res

无重复字符的最长子串，T3

def lengthOfLongestSubstring(s):
    left = 0
    right = 0
    window = dict()
    res = 0
    while right < len(s):
        c = s[right]
        right += 1
        if c in window:
            window[c] += 1
        else:
            window[c] = 1
        while window[c] > 1:
            d = s[left]
            left += 1
            window[d] -= 1
        res = max(res,right-left)
    return res

基本二分搜索 二分查找框架

def binarySearch(nums,target):
    left = 0
    right = ...
    while (...):
        mid = left + (right - left) // 2 #可以有效防止left和right直接相加导致溢出
        if nums[mid] == target:
            ...
        elif(nums[mid] < target):
            left = ...
        elif(nums[mid] > target):
            right = ...
    return

二分查找，T704

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return -1

一些细节：

闭区间[left,right]：初始right=len(nums)-1；while用left<=right

左闭右开区间[left,right)：初始right=len(nums)；while用left

算法局限性：如果数组中含有相同的值，无法按要求取得第一个、最后一个等等。

寻找左侧边界的二分搜索

左闭右开：

def left_bound(nums,target):
    if len(nums) == 0:
        return -1
    left = 0
    right = len(nums)
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            right = mid
        elif nums[mid] < target:
            left = mid + 1
        elif nums[mid] > target:
            right = mid
    if left == len(nums):
        return -1
    return left if nums[left] == target else -1#nums中小于target的元素有几个

注：假如nums不含有target，那么有三种情况：

（1）nums = [2,3,5,7]，target = 1，算法返回0，nums中小于1的元素有0个

（2）nums = [2,3,5,7]，target = 8，算法返回4，nums中小于8的元素有4个

（3）nums = [2,3,5,7]，target = 4，算法返回2，nums中小于4的元素有2个

左闭右闭：

def left_bound(nums,target):
    left = 0
    right = len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            right = mid - 1
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    if (left >= len(nums)) or (nums[left] != target):
        return -1
    return left

寻找右侧边界的二分查找

左闭右开：

def right_bound(nums,target):
    if len(nums) == 0:
        return -1
    left = 0
    right = len(nums)
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            left = mid + 1
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid
    if left == 0:
        return -1
    return left - 1 if nums[left - 1] == target else -1

左闭右闭：

def right_bound(nums,target):
    left = 0
    right = len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            left = mid + 1
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    if (right < 0) or nums[right] != target:
        return -1
    return right

在排序数组中查找元素的第一个和最后一个位置，T34

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        if len(nums) == 0:
            return [-1,-1]
        left = 0
        right = len(nums) - 1
        if (nums[left] > target) or (nums[right] < target):
            return [-1,-1]
        #寻找左侧边界
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                right = mid - 1
            elif nums[mid] < target:
                left = mid + 1
            elif nums[mid] > target:
                right = mid - 1
        if nums[left] == target:
            start = left
        else:
            return [-1,-1]
        #寻找右侧边界
        left = 0
        right = len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                left = mid + 1
            elif nums[mid] < target:
                left = mid + 1
            elif nums[mid] > target:
                right = mid - 1
        if nums[right] == target:
            end = right
        else:
            return [-1,-1]
        return [start,end]

二分搜索的应用

什么问题可以用二分搜索算法解决？

要从题目中抽象出自变量x，关于x的函数f(x)，以及目标值targetf(x)关于x单调目标是计算f(x)==target的x的值

爱吃香蕉的珂珂，T875

题目：有N堆香蕉，第i堆有piles[i]根。珂珂可以决定她吃香蕉的速度K（根/小时），每个小时，她将会选择一堆香蕉，从中吃掉K根，如果这堆香蕉少于K根，她将吃掉这堆所有香蕉，然后这一小时内不会再吃更多香蕉。珂珂喜欢慢慢吃，返回她在H小时内吃掉所有香蕉的最小速度K（整数）

def minEatingSpeed(piles,H):
    """
    x:吃香蕉速度，每小时x根
    f(x)：吃完所有香蕉所需时间
    """
    def f(piles,x):
        hours = 0
        for pile in piles:
            hours += pile // x
            if pile % x > 0:
                hours += 1
        return hours
    #f是x的递减函数，要求使得f(x)<=H的最小的x
    left = 1
    right = max(piles)
    while left <= right:
        mid = left + (right - left) // 2
        if f(piles,mid) == H:
            right = mid - 1
        elif f(piles,mid) > H:
            left = mid + 1
        elif f(piles,mid) < H:
            right = mid - 1
    return left

在D天内送达包裹的能力，T1011

class Solution:
    def shipWithinDays(self, weights: List[int], days: int) -> int:
        #运载能力为x时需要的天数，递减
        def f(weights,x):
            num = 0 #天数
            w = 0 #当前货物重量
            for weight in weights:
                w += weight
                if w > x:
                    num += 1
                    w = weight
            return num + 1
        # f(x)<=days的x的最小值
        left = max(weights)
        right = sum(weights)
        while left <= right:
            mid = left + (right - left) // 2
            if f(weights,mid) <= days:
                right = mid - 1
            else:
                left = mid + 1
        return left

分割数组的最大值，T410

题目：给定一个非负整数数组nums，将数组分成m个非空的连续子数组，使得这m个子数组各自和的最大值最小。

#限制一个最大子数组和max，至少可以将nums分成几个子数组
#那么如果我们找到一个最小max值，满足split(nums,max)和m相等，那这个max就是题目要的
#m越大max越小
#max为自变量，f(max)=m的最小max
def splitArray(nums,m):      
	
	def split(nums,max_):
        count = 0 #分成几组
        sumnum = 0 #当前和
        for num in nums:
            sumnum += num
            if sumnum > max_:
                count += 1
                sumnum = num
        return count + 1
    left = max(nums)
    right = sum(nums)
    while left <= right:
        mid = left + (right - left) // 2
        n = split(nums,mid)
        if n <= m:
            right = mid - 1
        else:
            left = mid + 1
	return left

田忌赛马——优势洗牌，T870

题目：给定长度相等的数组A和B，A[i] > B[i]的数目说明A相对于B的优势。要求返回A的任意排列，使其相对于B的优势最大化。

方法：将二者按照战斗力排序，然后按照排名一一对比，如果A能赢那就比，赢不了就换个垫底的送人头，保存实力。

注意计算结果的顺序依赖nums2的顺序，所以nums2中元素的顺序不能改变，不能直接对其排序，而是利用其它数据结构来辅助。

class Solution:
    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:
        n = len(nums1)

        #nums1升序排序
        nums1.sort()

        #nums2降序排序，(值，索引)
        new2 = []
        for i in range(n):
            heapq.heappush(new2,(-nums2[i],i))
        
        res = [0 for i in range(n)]
        left = 0
        right = n - 1
        while new2:
            val,i = heapq.heappop(new2)
            if nums1[right] > - val:
                res[i] = nums1[right]
                right -= 1
            else:
                res[i] = nums1[left]
                left += 1
        
        return res

注意：堆排序的结果只是保证第一个最小，并不是整个数组升序排列！！

常数时间删除/查找数组中任意元素 常数时间插入、删除和获取随机元素，T380

class RandomizedSet:
    def __init__(self):
        #存储元素的值
    	self.nums = []
        #元素：索引
        self.valToIndex = dict()
        
    #val不存在则插入，返回True；val存在返回False
    def insert(self,val):
        if val in self.valToIndex:
            return False
        self.valToIndex[val] = len(self.nums)
        self.nums.append(val)
        return True
    
    #val存在则删除，返回True；val不存在返回False
    def remove(self,val):
        if val not in self.valToIndex:
            return False
        index = self.valToIndex[val]
        self.valToIndex[self.nums[-1]] = index
        self.valToIndex.pop(val)
        self.nums[index],self.nums[-1] = self.nums[-1],self.nums[index]
        self.nums.pop()
        return True
        
    #随机返回现有集合中的一项（每个元素有相同概率）
    def getRandom(self):
        return self.nums[random.randint(0,len(self.nums)-1)]

TWOSUM问题 TWOSUM Ⅰ，T1

基本形式：给定一个数组和整数target，保证数组中存在两个数的和为target，要求返回这两个数的索引

def twoSum(nums,target):
    n = len(nums)
    #构建哈希表，元素：索引
    index = dict()
    for i in range(n):
        index[nums[i]] = i#有相同元素时，会自动更新到最后一个索引，但后面用到是从前往后的，所以不用担心这个问题
    for i in range(n):
        other = target - nums[i]
        if (other in index) and (index[other] != i):
            return [i,index[other]]
    return [-1,-1]

官方：

def twoSum(nums,target):
    n = len(nums)
    index = dict()
    for i in range(n):
        other = target - nums[i]
        if other in index:
            return [index[other],i]
        index[nums[i]] = i
    return [-1,-1]

TwoSum Ⅱ，T170

class TwoSum:
    def __init__(self):
        self.freq = []
        
    #向数据结构添加一个数，O(1)
    def add(self,number):
    	if number in self.freq:
            self.freq[number] += 1
        else:
            self.freq[number] = 1
    #寻找数据结构中是否存在一对整数，使两数之和与给定的值相等。存在返回True，不存在返回False，O(N)
    def find(self,value):
        for key in self.freq:
            other = value - key
            if (other == key) and (freq[key] > 1):
                return True
            elif (other != key) and (other in freq):
                return True
        return False

如果find使用频繁，如何优化？

class TwoSum:
    def __init__(self):
        self.nums = []
        self.sum = set()
        
    def add(self,number):
        #记录所有可能和
        for n in self.nums:
            self.sum.add(n+number)
        self.nums.append(number)
    
    def find(self,value):
        return value in self.sum

数组去重问题 去除重复字母，T316

题目：给你一个仅包含小写字母的字符串，请去除重复字母，使每个字母只出现一次。需保证返回结果的字典序最小（要求不能打乱其他字符的相对位置）

def removeDuplicateLetters(s):
    stk = []
    #count记录s中的字符的数量，可以看到之后还有没有同样的字母
    count = [0 for i in range(256)]
    for ch in s:
        count[ord(ch)] += 1
    #instack记录s中字符是否在栈里
    instack = [False for i in range(256)]
    for c in s:
        count[ord(c)] -= 1
        if instack[ord(c)]:
            continue
        while (stk) and c < stk[-1]:
            if count[ord(stk[-1])] == 0:
                break
            inStack[ord(stk.pop())] = False
        stk.append(c)
        inStack[ord(c)] = True
    return "".join(stk)

原地修改数组

对于数组来说，在尾部插入、删除元素比较高效，时间复杂度O(1)；在中间或开头插入、删除元素，会涉及数据搬移，时间复杂度O(N)。

有序数组去重，T26

原地删除排序数组中重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

def removeDuplicates(nums):
    if len(nums) == 0:
        return 0
    slow = 0
    fast = 0
    while fast < len(nums):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]
        fast += 1
    return slow + 1

有序链表去重，T83

def deleteDuplicates(head):
    if (not head) or (not head.next):
        return head
    slow = head
    fast = head
    while fast:
        if slow.val != fast.val:
            slow.next = fast
            slow = slow.next
        fast = fast.next
    slow.next = None
    return head

移除元素，T27

原地移除数组nums中所有数值等于val的元素，并返回移除后数组的新长度。

def removeElement(nums,val):
    slow = 0
    fast = 0
    while fast < len(nums):
        if nums[fast] != val:
            nums[slow] = nums[fast]
            slow += 1
        fast += 1
    return slow

移动零，T283

将数组nums中所有值为0的元素移到数组末尾

def moveZeroes(nums):
    slow = 0
    fast = 0
    while fast < len(nums):
        if nums[fast] != 0:
            nums[slow] = nums[fast]
            slow += 1
        fast += 1
    for i in range(slow,len(nums)):
        nums[i] = 0