2143-2つのアレイの合計

5383 ワード
Binary Search plzrun baekjoon テキストリンク

📚 2143-2つのアレイの合計


2列の和
 

理解する


問題は,1つのプログラムを記述し,2つの配列を加算してTのすべてのサブ配列対の個数を求めることである.
これは逐次漸進的な探索であり,徹底的に探索する必要がある場合である.
配列の和:A[i] + ... + A[j]その間の和を求める問題.
探索を順次行い,区間和を求める際にディックシャーナを用いる.
このような問題を解決するには、現在のAの和をディックシーケンスに格納します.key : 부 배열의 합, value : 횟수ディクシャナにデータを入力していない場合(回数が0の場合)
使用딕셔너리.get메서드可.
  • A結果をディックコーナーに保存後
  • T - B賈A keyに存在する場合は、個数+でよい.
    •  

    ソース

    import sys

read = sys.stdin.readline

t = int(read())

n = int(read())
a = list(map(int, read().split()))
m = int(read())
b = list(map(int, read().split()))

answer = 0

dist = dict()

for i in range(n):
    cur_sum = 0
    for j in range(i, n):
        cur_sum += a[j]
        dist[cur_sum] = dist.get(cur_sum, 0) + 1

for i in range(m):
    cur_sum = 0
    for j in range(i, m):
        cur_sum += b[j]
        answer += dist.get(t-cur_sum, 0)

print(answer)
    クエリN+1問題
    Spark-1.4.0スタンドアロン導入テスト