Leetcode 930：和相同的二元子数组

冷不防 2022-01-25 23:19 69阅读 0赞

1、在由若干 `0` 和 `1` 组成的数组 `A` 中，有多少个和为 `S` 的**非空**子数组。

输入：A = \[1,0,1,0,1\], S = 2  
输出：4  
解释：  
如下面所示，有 4 个满足题目要求的子数组：  
\[1,0,1,0**,**1\]  
\[1,0,1,0,1\]  
\[1,0,1,0,1\]  
\[1,0,1,0,1\]

这个问题和之前的[Leetcode 560：和为K的数组（最详细的解法！！！）][Leetcode 560_K]非常类似。

可以通过Prefix sum前缀和来求解。假设我们令P\[i\] = A\[0\] + A\[1\] + ... + A\[i-1\]和P\[j\] = A\[0\] + A\[1\] + ... + A\[j-1\]，那么P\[j\] - P\[i\] = A\[i\] + A\[i+1\] + ... + A\[j-1\]。如果P\[j\] - P\[i\] == S的话，那么\[i,j\]就是我们需要的区间。所以我们对于每个j，我们只要计算有多少个i使得P\[j\] - P\[i\] == S，这样我们就得到了以P\[j\]作为右区间并且和为S的区间数。对于A中的每个元素都做同样的处理，最有将所有的结果相加即可。

具体实现上，我们通过hash\_map记录P\[j\]。初始化的时候要注意一个细节，对于dict\[0\]=1。为什么？因为当P\[j\]==S时，P\[i\]=0并且此时我们的result=1。

class Solution:
        def numSubarraysWithSum(self, A, S):
            """
            :type A: List[int]
            :type S: int
            :rtype: int
            """
            result, cur_sum = 0, 0
            sum_dict = {0:1}
            for num in A:
                cur_sum += num
                if cur_sum - S in sum_dict:
                    result += sum_dict[cur_sum - S]
                if cur_sum in sum_dict:
                    sum_dict[cur_sum] += 1
                else:
                    sum_dict[cur_sum] = 1
                    
            return result

from：[https://blog.csdn.net/qq\_17550379/article/details/83547444][https_blog.csdn.net_qq_17550379_article_details_83547444]

2、给定一个字符串 `s`，找到 `s` 中最长的回文子串。你可以假设 `s` 的最大长度为 1000。

**示例 1：**

输入: "babad"
    输出: "bab"
    注意: "aba" 也是一个有效答案。

1、暴力搜索：

class Solution(object):
        def longestPalindrome(self, s):
            """
            :type s: str
            :rtype: str
            """     
            maxlen=0 
            for i in range(len(s)):
                temp=''
                for j in range(i+1,len(s)):
                    temp+=s[j]
                    if(temp==temp[::-1]):
                        if len(temp)>maxlen:
                            maxlen=len(temp)
                            tem=temp
            return tem

2、从最长字符串开始判别，这里的每一次循环其实是定义了不同的字符串长度

class Solution(object):
        def longestPalindrome(self, s):
            """
            :type s: str
            :rtype: str
            """
            n = len(s)
            for i in range(n):
                start = 0
                end = n - i
                while end <= n:
                    sub_string = s[start:end]
                    if sub_string == sub_string[::-1]:
                        return sub_string
                    start += 1
                    end += 1

[Leetcode 560_K]: https://blog.csdn.net/qq_17550379/article/details/83510121
[https_blog.csdn.net_qq_17550379_article_details_83547444]: https://blog.csdn.net/qq_17550379/article/details/83547444