Leetcode 523. Continuous Subarray Sum

深碍√TFBOYSˉ_ 2022-09-27 00:26 140阅读 0赞

有趣的dp

我们要求的是num\[L\] + num\[L+1\] + … + num\[R\] mod k 是否等于零。

所以我求一个前缀和A\[L\] + A\[L+1\] + … + A\[R\] = P\[R+1\] - P\[L\]

则我们要求 P\[R+1\] - P\[L\] mod k = 0

那么我们现在对每一个P\[i\] mod k，则只需要判断p\[R+1\] - P\[L\]是否为零，也就是是否存在两个相同的P\[i\]且距离相差2以上。

同时根据鸽巢原理，当n>=2\*k时，必然存在3个P\[i\]相同，也就是必然是可行的。

# -*- coding: utf-8 -*-
    # @Author: HaonanWu
    # @Date: 2017-03-06 20:56:21
    # @Last Modified by: HaonanWu
    # @Last Modified time: 2017-03-06 20:56:21
    
    class Solution(object):
        def checkSubarraySum(self, nums, k):
            """ :type nums: List[int] :type k: int :rtype: bool """
            if k == 0:
                # if two continuous zeros in nums, return True
                # time O(n)
                for i in range(0, len(nums) - 1):
                    if nums[i] == 0 and nums[i+1] == 0:
                        return True
                return False
    
            k = abs(k)
            if len(nums) >= k * 2:
                return True
    
            P = [0]
            for x in nums:
                v = P[-1] + x
                v %= k
                P.append(v)
    
            seen = set()
            for i in xrange(len(P) - 3, -1, -1):
                seen.add(P[i+2])
                if P[i] in seen:
                    return True
            return False

发表评论取消回复

表情：

评论列表（有 0 条评论，140人围观）

还没有评论，来说两句吧...

相关阅读

相关 Leetcode 523. Continuous Subarray Sum

有趣的dp 我们要求的是num\[L\] + num\[L+1\] + … + num\[R\] mod k 是否等于零。所以我求一个前缀和A\[L\] + A\[L+1

深碍√TFBOYSˉ_/ 2022年09月27日 00:26/ 0 赞/ 141 阅读

相关 leetcode 523. Continuous Subarray Sum | 523. 连续的子数组和（同余定理）

题目 [https://leetcode.com/problems/continuous-subarray-sum/][https_leetcode.com_proble

快来打我*/ 2022年09月12日 05:52/ 0 赞/ 192 阅读

相关 leetcode 209. Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length

电玩女神/ 2022年08月20日 15:15/ 0 赞/ 154 阅读

相关 [leetcode]209. Minimum Size Subarray Sum -- JavaScript 代码

/ @param {number} s @param {number[]} nums @return {number} / var minSubArray

清疚/ 2022年07月17日 03:12/ 0 赞/ 47 阅读

相关 LeetCode209—Minimum Size Subarray Sum

终于不用找实习了，恢复一下学习的节奏。原题 [LeetCode209][] Given an array of n positive integers and a

约定不等于承诺〃/ 2022年06月18日 09:41/ 0 赞/ 107 阅读

相关 [leetcode]: 581. Shortest Unsorted Continuous Subarray

1.题目 Given an integer array, you need to find one continuous subarray that if you onl

骑猪看日落/ 2022年06月14日 10:07/ 0 赞/ 131 阅读

相关 leetcode 523. Continuous Subarray Sum 子数组和 + 动态规划DP

Given a list of non-negative numbers and a target integer k, write a function to check i

水深无声/ 2022年06月03日 03:18/ 0 赞/ 160 阅读

相关 581. Shortest Unsorted Continuous Subarray

Given an integer array, you need to find one continuous subarray that if you only so

墨蓝/ 2022年06月02日 10:23/ 0 赞/ 106 阅读

相关 leetcode689. Maximum Sum of 3 Non-Overlapping Subarrays

In a given array nums of positive integers, find three non-overlapping subarrays with ma

た入场券/ 2022年05月31日 23:18/ 0 赞/ 150 阅读

相关 [LintCode] Continuous Subarray Sum 连续子数组之和

Given an integer array, find a continuous subarray where the sum of numbers is the bigge

短命女/ 2022年02月01日 09:15/ 0 赞/ 171 阅读