1.两数之和560.和为K的子数组1248.统计“美丽子数组”437.路径和III1.两个数之和给定一个整数数组nums和一个目标值target，请在数组中找到和为目标值的两个整数，并返回它们的数组下标。您可以假设每个输入只有一个答案。但是，数组中的同一个元素不能使用两次。示例：给定nums=[2,7,11,15]，target=9，因为nums[0]+nums[1]=2+7=9，返回[0,1]难度：第一次容易For接触过这类话题的人，最能想到的方法就是类似于冒泡排序的暴力算法，时间复杂度为$O(n^2)$，空间复杂度为$O(1)$。但是题目要求每个元素只能使用一次。很明显，上面的方法不符合要求，那怎么每个元素只能使用一次呢？回到最直观的思路，我们需要两个元素来判断：nums[i]+nums[j]=target?，如果每个元素只能使用一次，另一种思路，nums[j]=target-nums[i]，可以想象由于这道题的返回是提前保存target-nums[i]是一个索引，所以很自然的想到用字典来保存，然后判断是否nums[j就可以了]在字典里。按照思路，可以写出如下代码deftwoSum(self,nums:List[int],target:int)->List[int]:ifnotnumsorlen(nums)<2:return#usedictionary保存目标-nums[i]prefix_sum={}n=len(nums)foriinrange(n):如果nums[i]inprefix_sum:return[prefix_sum[nums[i]],i]prefix[target-nums[i]]=i时间复杂度$O(n)$，空间复杂度$O(n)$560。Sum是K的子数组给定一个整数数组和一个整数k，你需要找到数组中连续子数组的个数，其和为k。示例1：输入：nums=[1,1,1],k=2输出：2、[1,1]和[1,1]是两种不同的情况。说明：数组的长度为[1,20,000]。数组元素的范围是[-1000,1000]，整数k的范围是[-1e7,1e7]。一开始看到这个题目的时候，真的不知道怎么下手。主要问题是子数组可能包含负数。子数组的长度没有限制。现在假设子数组从$i$开始，到$j$结束，即$nums[i]+...+nums[j]=target$，而$nums[i]+...+nums[j]=sum(nums_{0,...,j})-sum(nums_{0,...,i-1})$因此，我们可以用字典来保存所有可能的连续子数组（上式右边部分），字典的值为和等于k的子数组的个数。这样，遍历一次就可以得到所有和为k的子数组的个数。按照这个思路，可以写成如下代码defsubarraySum(nums,k):ifnotnums:return0n=len(nums)res=0#从索引0到当前位置的数组prefix_sum=0#保存所有前缀和对应子数组的个数dicts={0:1}foriinrange(n):prefix_sum+=nums[i]ifprefix_sum-kindicts:res+=dicts[prefix_sum-k]#dicts[prefix_sum]=dicts.get(prefix_sum,0)+1returnres时间复杂度$O(n)$，空间复杂度$O(n)$1248。统计“美丽的子数组”给你一个整数数组nums和一个整数k。如果在一个连续的子数组中恰好有k个奇数，我们认为一个子数组是一个“美丽的子数组”。请返回此数组中“漂亮子数组”的数量。示例1：输入：nums=[1,1,2,1,1],k=3输出：2解释：包含3个奇数的子数组是[1,1,2,1]和[1,2,1,1].示例2：输入：nums=[2,4,6],k=1输出：0解释：该序列不包含任何奇数，因此不存在漂亮的子数组。示例3：输入：nums=[2,2,2,1,2,2,1,2,2,2],k=2输出：16提示：1<=nums.length<=500001<=nums[i]<=10^51<=k<=nums.length这道题的思路和上一题（560题）基本一样，只是把元素之和改为奇数，即本质上是一样的。defnumberOfSubarrays(nums,k):ifnotnumsorlen(nums)
