[BOJ]1253-いいね

4721 ワード
アルゴリズム#アルゴリズム# ダブルポインタ boj テキストリンク
質問リンク
1253-いいわ
問題の説明
N個の数のうち、ある数を別の数の2個の数の和として表すことができる場合、その数を「良い(GOOD)」と呼ぶ.
N個の数があれば、その中の良い数を出力します.
数の位置が異なり、値が同じでも異なる数です.
問題を解く
ダブルポインタを使用してリリースします.
  • Nの数字、
    • のソート
  • 0個からN−1個までの数は,二重ポインタで良い数か否かを判断する.
    2.1 start,endを0,N-1にする
    2.2 A[start]+A[end]=A[i]面割込み
    2.3>A[i]面end--
    2.4しかしこのように実現すれば,0を含むリストに対しては,0以外のすべての数が良い数となる.チェックstartまたはendがすぐにチェックされない部分を追加する必要があります!
    コード全体を以下に示します.
    import sys

input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
A.sort()

answer = 0
for i in range(len(A)):
    start, end = 0, len(A)-1
    while start < end:
        if start == i:
            start += 1
        elif end == i:
            end -= 1
        else:
            if A[start]+A[end] == A[i]:
                answer += 1
                break
            elif A[start]+A[end] < A[i]:
                start += 1
            else:
                end -= 1

print(answer)
    • ノードエクスプレスのアプリケーションのための
    Android浅談微信支払い+支付宝支払い