leecode刷题笔记（三）

2020-06-25

根据不同的解答方法，总结leecode不同题型。

方法三：双指针

通过左右两个双指针，在满足一定情况的条件下移动，计数。

从开头一起开始的双指针。
一个从开头向后走，一个从结尾向前走的双指针。

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]]:
        n=len(nums)
        res=[]
        if(not nums or n<3):
            return []
        nums.sort()
        res=[]
        for i in range(n):
            if(nums[i]>0):
                return res
            if(i>0 and nums[i]==nums[i-1]):
                continue
            L=i+1
            R=n-1
            while(L<R):
                if(nums[i]+nums[L]+nums[R]==0):
                    res.append([nums[i],nums[L],nums[R]])
                    while(L<R and nums[L]==nums[L+1]):
                        L=L+1
                    while(L<R and nums[R]==nums[R-1]):
                        R=R-1
                    L=L+1
                    R=R-1
                elif(nums[i]+nums[L]+nums[R]>0):
                    R=R-1
                else:
                    L=L+1
        return res

1248. 统计「优美子数组」

给你一个整数数组 nums 和一个整数 k。

如果某个连续子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。

请返回这个数组中「优美子数组」的数目。

示例：

1
2
3

输入：nums = [1,1,2,1,1], k = 3
输出：2
解释：包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1] 。

解答：

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        left=0;right=0
        left_e=0;right_e=0 # even
        sum_n=0
        sum_num=0
        for right in range(len(nums)):
            if nums[right]%2 == 1:
                sum_n += 1
                if sum_n == k:
                    left_e=0
                    while sum_n == k:
                        left_e += 1
                        if nums[left] % 2 == 1:
                            sum_n -= 1
                        left += 1
            sum_num+=left_e
        return sum_num

904. 水果成篮

在一排树中，第 i 棵树产生 tree[i] 型的水果。
你可以从你选择的任何树开始，然后重复执行以下步骤：

把这棵树上的水果放进你的篮子里。如果你做不到，就停下来。
移动到当前树右侧的下一棵树。如果右边没有树，就停下来。

请注意，在选择一颗树后，你没有任何选择：你必须执行步骤 1，然后执行步骤 2，然后返回步骤 1，然后执行步骤 2，依此类推，直至停止。

你有两个篮子，每个篮子可以携带任何数量的水果，但你希望每个篮子只携带一种类型的水果。
用这个程序你能收集的水果总量是多少？

示例 1：

1
2
3

输入：[1,2,1]
输出：3
解释：我们可以收集 [1,2,1]。

示例 2：

输入：[0,1,2,2]
输出：3
解释：我们可以收集 [1,2,2].
如果我们从第一棵树开始，我们将只能收集到 [0, 1]。

解答：

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        L=0;R=0
        a=[tree[0]]
        num=0
        max_num=0
        while R<len(tree):
            if len(a)==1 and (tree[R] not in a):
                a.append(tree[R])
            if tree[R] not in a:
                max_num=max(num,max_num)
                num = R-L
                a = [tree[L],tree[R]]
            num+=1
            if tree[R]!=tree[L]:
                L=R
            R+=1
        
        max_num=max(num,max_num)
        return max_num