2003番数字の和2

8706 ワード
インプリメンテーション ダブルポインタ boj テキストリンク
質問元:https://www.acmicpc.net/problem/2003

思考過程.


線形リストの連続値を要素として指定した値と比較します.O(n)で解けるみたい!
与えられた値と比較する要素値を収集するlistをsと呼ぶ.
s+newがMより小さい場合は、次の要素をクエリーして調査します.
s+newがMより大きい場合は、どうせsの最初の要素を削除します.newをクエリする場合、ss+newがMと値の場合、resultに1を加算します.
import sys

N,M = list(map(int,sys.stdin.readline().rstrip("\n").split()))
num = list(map(int,sys.stdin.readline().rstrip("\n").split()))
s = [0]
result=0

for i in range(N) :
    if num[i]>M :
        s=[0]
        continue
    while sum(s)+num[i]>M :
        s.pop(0) #만약 모든 요소가 없다면? num[i]가 M보다 커
    s.append(num[i])
    if sum(s)==M :
        result+=1

print(result)
他の人の解より10倍の時間がかかります.より効率的に作成
かなりO(n)に減らして、sという配列を使うのではなく、本物の2つのポインタを使って、left、rightももっと長い時間を費やしました...他の人がどのように書いたかを参考にして、勉強します.
原理が似ているようです.私のようにpopを書くのではなく、直接二重ポインタを利用してjust数字で計算します.実際,コードを分解した後,二重ポインタを直接使用するのではなく,スタックと二重ポインタの原理を用いて抽象的に記述した.
import sys

N,M = list(map(int,sys.stdin.readline().rstrip("\n").split()))
num = list(map(int,sys.stdin.readline().rstrip("\n").split()))
left,s = 0,0
result=0

for i in range(N) :
    if num[i]>M :
        left =i+1
        continue
    s+=num[i]
    while s>M :
        s-=num[left]
        left+=1
    if s==M :
        result+=1

print(result)
left,right変数でtopointを使うことができますが、初めて着目した方法で他人の考えや理論を修正して、私のもっと重要なものにすることができると思いますので、私は私の方法を堅持して変えました.ドアを利用するのではなく、最初の様子で、一つ一つ進んで、前の部分を計算します.疑問iに対して二重ポインタの正しい役割を果たした.

比較結果



すごいスピード~!!
スタックではなく整数型で直接計算します.これは確かにもっと速いListはかなり役に立ち、便利ですが、あまり依存しないでください.
[21.07.14] Access Modifier
白俊-有機白菜[112]