Leetcode-接頭辞とシリーズ
1.両数の和 560.とKのサブ配列 1248.統計「優美なサブ配列」 437.経路総和III
1.両数の和
整数配列numsとターゲット値targetを指定します.この配列でターゲット値の2つの整数を見つけて、その配列の下付きを返します.
入力ごとに1つの答えしか対応しないと仮定できます.ただし、配列内の同じ要素は2回使用できません.
例:
与えられたnums=[2,7,11,15],target=9
nums[0]+nums[1]=2+7=9なので[0,1]を返します
難易度:Easy
このようなタイプのテーマに初めて触れた人にとって、最も考えられる方法は、泡のソートのような暴力アルゴリズムであり、時間の複雑度は$O(n^2)$であり、空間の複雑度は$O(1)$である.
しかし、テーマは要素ごとに1回しか使用できないことを要求しています.明らかに上の方法は要求を満たすことができません.では、どのようにして要素ごとに1回しか使用できませんか.
最も直感的な考えに戻るには、nums[i]+nums[j]=target?という2つの要素が必要です.各要素が一度しか使用できない場合、考え方を変えるとnums[j]=target-nums[i]となり、target-nums[i]を先に保存することが考えられる本題ではインデックスを返すので、自然に辞書を使って保存することを考え、その後nums[j]が辞書にあるかどうかを判断すればよい.
考えに沿って、次のようなコードを書くことができます.
時間複雑度$O(n)$空間複雑度$O(n)$
560.とKのサブ配列
整数配列と整数kを指定するには、その配列とkの連続するサブ配列の個数を見つける必要があります.
例1:
入力:nums=[1,1,1],k=2
出力:2,[1,1]と[1,1]は2つの異なる場合である.
説明:
配列の長さは[1,20000]である.配列中の要素の範囲は[−1000,1000]であり、整数kの範囲は[−1 e 7,1 e 7]である.
最初はこの問題を見て、確かにどのように手をつけるか分かりませんが、主な問題は:のサブ配列に負の数が含まれる場合がある. は、サブ配列の長いを限定するものではない.
サブ配列の開始位置を$i$,終了位置を$j$,すなわち$nums[i]+...+と仮定するnums[j]=target$で$nums[i]+...+nums[j]=sum(nums_{0,...,j})-sum(nums_{0,...,i-1})$
したがって、1つの辞書で可能なすべての連続サブ配列(上式の右側の部分)と、kに等しいサブ配列の数とを保存することができる.
これにより、一度に遍歴することができ、kとなるすべてのサブ配列の個数を得ることができる.この考え方では、次のようなコードを書くことができます.
時間複雑度$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 <= 50000 1 <= nums[i] <= 10^5 1 <= k <= nums.length
この問題は前の問題(560問題)の構想と基本的に一致しているが、要素と奇数の数に変わっただけで、本質的には同じである.
時間複雑度$O(n)$空間複雑度$O(n)$
437.経路総和III
ツリーが与えられ、各ノードに整数値が格納されます.
パスと指定した値に等しいパスの合計数を見つけます.
パスはルートノードから開始する必要もなく、リーフノードで終了する必要もありませんが、パスの方向は下向きでなければなりません(親ノードから子ノードまでのみ).
ツリーは1000ノードを超えず、ノードの数値範囲は[-10000001000000]の整数です.
例:
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
この問題は接頭辞と二叉木での応用と見なすことができ,構想はやはり同じである.
時間複雑度$O(n)$空間複雑度$O(n)$
まとめ
接頭辞和の方法は、通常、シーケンスにおける条件を満たす連続サブシーケンスの数を解決するために用いるが、このような問題に対しては、通常、辞書を用いて各接頭辞とその出現回数を記録し、毎回(現在の接頭辞と-target)が辞書にあるかどうかを判断するだけで、もしあるならば、結果にその接頭辞と対応する個数を加える.辞書に追加する.
なお、接頭辞および辞書は、条件を満たす連続サブ配列が0から始まる場合、現在の接頭辞および連続サブ配列の和に等しい場合、(現在の接頭辞および-target)=0は必ずしも辞書に存在しないため、通常{0,1}に初期化する.
以上の内容は、誤りや不当な点があれば、コメントエリアで直接指摘することができる.教えていただき、ありがとうございます.
1.両数の和
整数配列numsとターゲット値targetを指定します.この配列でターゲット値の2つの整数を見つけて、その配列の下付きを返します.
入力ごとに1つの答えしか対応しないと仮定できます.ただし、配列内の同じ要素は2回使用できません.
例:
与えられたnums=[2,7,11,15],target=9
nums[0]+nums[1]=2+7=9なので[0,1]を返します
難易度:Easy
このようなタイプのテーマに初めて触れた人にとって、最も考えられる方法は、泡のソートのような暴力アルゴリズムであり、時間の複雑度は$O(n^2)$であり、空間の複雑度は$O(1)$である.
しかし、テーマは要素ごとに1回しか使用できないことを要求しています.明らかに上の方法は要求を満たすことができません.では、どのようにして要素ごとに1回しか使用できませんか.
最も直感的な考えに戻るには、nums[i]+nums[j]=target?という2つの要素が必要です.各要素が一度しか使用できない場合、考え方を変えるとnums[j]=target-nums[i]となり、target-nums[i]を先に保存することが考えられる本題ではインデックスを返すので、自然に辞書を使って保存することを考え、その後nums[j]が辞書にあるかどうかを判断すればよい.
考えに沿って、次のようなコードを書くことができます.
def twoSum(self, nums: List[int], target: int) -> List[int]:
if not nums or len(nums) < 2:
return
# target - nums[i]
prefix_sum = {}
n = len(nums)
for i in range(n):
if nums[i] in prefix_sum:
return [prefix_sum[nums[i]], i]
prefix[target-nums[i]] = i
時間複雑度$O(n)$空間複雑度$O(n)$
560.とKのサブ配列
整数配列と整数kを指定するには、その配列とkの連続するサブ配列の個数を見つける必要があります.
例1:
入力:nums=[1,1,1],k=2
出力:2,[1,1]と[1,1]は2つの異なる場合である.
説明:
配列の長さは[1,20000]である.配列中の要素の範囲は[−1000,1000]であり、整数kの範囲は[−1 e 7,1 e 7]である.
最初はこの問題を見て、確かにどのように手をつけるか分かりませんが、主な問題は:
サブ配列の開始位置を$i$,終了位置を$j$,すなわち$nums[i]+...+と仮定するnums[j]=target$で$nums[i]+...+nums[j]=sum(nums_{0,...,j})-sum(nums_{0,...,i-1})$
したがって、1つの辞書で可能なすべての連続サブ配列(上式の右側の部分)と、kに等しいサブ配列の数とを保存することができる.
これにより、一度に遍歴することができ、kとなるすべてのサブ配列の個数を得ることができる.この考え方では、次のようなコードを書くことができます.
def subarraySum(nums, k):
if not nums:
return 0
n = len(nums)
res = 0
# 0
prefix_sum = 0
#
dicts = {0: 1}
for i in range(n):
prefix_sum += nums[i]
if prefix_sum - k in dicts:
res += dicts[prefix_sum - k]
#
dicts[prefix_sum] = dicts.get(prefix_sum, 0) + 1
return res
時間複雑度$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
ヒント:
この問題は前の問題(560問題)の構想と基本的に一致しているが、要素と奇数の数に変わっただけで、本質的には同じである.
def numberOfSubarrays(nums, k):
if not nums or len(nums) < k:
return 0
res = 0
# ,
dicts = {0: 1}
# 0 ,
prefix_sum = 0
n = len(nums)
for i in range(n):
if nums[i] % 2:
prefix_sum += 1
if prefix_sum - k in dicts:
res += dicts[prefix_sum - k]
if prefix_sum not in dicts:
dicts[prefix_sum] = 0
# prefix_sum 1
dicts[prefix_sum] += 1
return res
時間複雑度$O(n)$空間複雑度$O(n)$
437.経路総和III
ツリーが与えられ、各ノードに整数値が格納されます.
パスと指定した値に等しいパスの合計数を見つけます.
パスはルートノードから開始する必要もなく、リーフノードで終了する必要もありませんが、パスの方向は下向きでなければなりません(親ノードから子ノードまでのみ).
ツリーは1000ノードを超えず、ノードの数値範囲は[-10000001000000]の整数です.
例:
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
10
/ \
5 -3
/ \ \
3 2 11
/ \ \
3 -2 1
3。 8 :
1. 5 -> 3
2. 5 -> 2 -> 1
3. -3 -> 11
この問題は接頭辞と二叉木での応用と見なすことができ,構想はやはり同じである.
def pathSum(self, root, sum):
self.dicts = {0: 1}
self.res = 0
def helper(root, prefix_sum, sum):
if not root:
return 0
prefix_sum += root.val
if prefix_sum - sum in self.dicts:
self.res += self.dicts[prefix_sum - sum]
self.dicts[prefix_sum] = self.dicts.get(prefix_sum, 0) + 1
helper(root.left, prefix_sum, sum)
helper(root.right, prefix_sum, sum)
# Note: , 1
self.dicts[prefix_sum] -= 1
helper(root, 0, sum)
return res 時間複雑度$O(n)$空間複雑度$O(n)$
まとめ
接頭辞和の方法は、通常、シーケンスにおける条件を満たす連続サブシーケンスの数を解決するために用いるが、このような問題に対しては、通常、辞書を用いて各接頭辞とその出現回数を記録し、毎回(現在の接頭辞と-target)が辞書にあるかどうかを判断するだけで、もしあるならば、結果にその接頭辞と対応する個数を加える.辞書に追加する.
なお、接頭辞および辞書は、条件を満たす連続サブ配列が0から始まる場合、現在の接頭辞および連続サブ配列の和に等しい場合、(現在の接頭辞および-target)=0は必ずしも辞書に存在しないため、通常{0,1}に初期化する.
以上の内容は、誤りや不当な点があれば、コメントエリアで直接指摘することができる.教えていただき、ありがとうございます.