サブ配列の和
1130 ワード
トピックの説明:整数配列を指定し、ゼロのサブ配列を見つけます.コードは要求を満たすサブ配列の開始位置と終了位置を返すべきです
例:[-3,1,2,-3,4]を与える、[0,2]または[1,3]を返す.
和が0のサブ配列を求めると,貧乏は当然解決できる.しかし、効率が低すぎる.だから、私はここで空間で時間を交換する方法を使いました:ハッシュテーブル(ハッシュテーブルとは、ここではキー値ペアからなるリスト、つまりpythonの中の辞書と簡単に理解できます)
どういう意味ですか.配列の和(上位1位の和,上位2位の和,上位3位の和)を順に求めるとすると,また,求めた和と対応する上位ビットを1つのハッシュテーブルに格納する(キーは和,値は上位ビットに対応する).前のnビットの和を求めると、前のある和(例えば、前のmビットの和)と等しいことがわかります.これは、配列のm+1ビットからnビットまでのすべての要素の和が0であることを意味します.これにより,一度の遍歴による問題解決が実現される.
コードは次のとおりです.
例:[-3,1,2,-3,4]を与える、[0,2]または[1,3]を返す.
和が0のサブ配列を求めると,貧乏は当然解決できる.しかし、効率が低すぎる.だから、私はここで空間で時間を交換する方法を使いました:ハッシュテーブル(ハッシュテーブルとは、ここではキー値ペアからなるリスト、つまりpythonの中の辞書と簡単に理解できます)
どういう意味ですか.配列の和(上位1位の和,上位2位の和,上位3位の和)を順に求めるとすると,また,求めた和と対応する上位ビットを1つのハッシュテーブルに格納する(キーは和,値は上位ビットに対応する).前のnビットの和を求めると、前のある和(例えば、前のmビットの和)と等しいことがわかります.これは、配列のm+1ビットからnビットまでのすべての要素の和が0であることを意味します.これにより,一度の遍歴による問題解決が実現される.
コードは次のとおりです.
class Solution:
"""
@param nums: A list of integers
@return: A list of integers includes the index of the first number
and the index of the last number
"""
def subarraySum(self, nums):
sum = 0
# hash : —— 0; —— -1
hash_table = {0:-1}
n = len(nums)
for i in range(n):
sum += nums[i]
if sum in hash_table:
return [hash_table[sum] + 1, i]
hash_table[sum] = i
# write your code here
は、最初の要素で始まるサブ配列と0の場合を処理するために、10行目にハッシュテーブルに前置ビットを追加することに注意しなければならない.よく理解して