• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            Uriel's Corner

            Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
            posts - 0, comments - 50, trackbacks - 0, articles - 594
            給定一串數nums和整數k,問這串數的子串和可以被k整除的子串(連續的一段)有多少
            參考了Discussion:
            先預處理prefix_sum(%k之后的值)
            如果子串nums[i]~num[j]之和可以被k整除,說明prefix_sum[i] = prefix_sum[j],于是用dict存各種prefix_sum的可能性有多少,最后
            ans = sum(prefix_sum[x] * (prefix_sum[x]- 1) / 2), x=0~k-1
            因為是C(n, 2)的組合數,所以不必等所有prefix_sum計算完再一個個算,在掃描nums,計算當前prefix_sum的時候順便累加即可
            注意初始化prefix_sum[0] = 1,因為一個數都不取的話和為0


             1 #974
             2 #Runtime: 232 ms (Beats 92.68%)
             3 #Memory: 16.8 MB (Beats 37.80%)
             4 
             5 class Solution(object):
             6     def subarraysDivByK(self, nums, k):
             7         """
             8         :type nums: List[int]
             9         :type k: int
            10         :rtype: int
            11         """
            12         pre_sum = defaultdict(int)
            13         t, ans = 0, 0
            14         pre_sum[0] = 1
            15         for i in nums:
            16             t = (t + i) % k
            17             pre_sum[t] += 1
            18             ans += pre_sum[t] - 1
            19         return ans
            久久66热人妻偷产精品9| 中文国产成人精品久久亚洲精品AⅤ无码精品 | 国产伊人久久| 亚洲国产成人精品久久久国产成人一区二区三区综 | 五月丁香综合激情六月久久| 狠狠色噜噜狠狠狠狠狠色综合久久| 国产免费福利体检区久久| 97视频久久久| 久久e热在这里只有国产中文精品99| 久久婷婷国产剧情内射白浆| 久久99热国产这有精品| 久久婷婷国产剧情内射白浆| 66精品综合久久久久久久| 亚洲欧美日韩中文久久| 久久亚洲AV无码西西人体| 色综合色天天久久婷婷基地| 一本色道久久88精品综合| 久久久综合香蕉尹人综合网| 69久久夜色精品国产69 | 国产精品禁18久久久夂久| 无码国内精品久久综合88| 国产精自产拍久久久久久蜜| 99久久99这里只有免费的精品| 国产精品久久久久久久app| 香蕉久久影院| 亚洲国产成人久久一区WWW| 精品久久久久久99人妻| 草草久久久无码国产专区| 久久久国产精品网站| 久久精品国产影库免费看| 久久亚洲私人国产精品| 亚洲色大成网站www久久九| 久久精品国产清自在天天线| 久久无码国产专区精品| 性高湖久久久久久久久AAAAA| 内射无码专区久久亚洲| 久久久这里只有精品加勒比| 四虎国产精品成人免费久久| 中文字幕无码av激情不卡久久| 性做久久久久久久久浪潮| 久久人与动人物a级毛片|