two pointer法

アルゴリズムを勉強したら、就活と研究に役立つと聞いたので、LeetCodeを始めて、とりあえずLeetCode75やるかと決めて、Easyは問題なかったんだが、meduim入ったあたりから、TLEが出て、なんじゃこりゃと思っていたら、どうやら、時間計算量ってのを考慮しなければいけないらしく、結構数学みたいな勉強が必要なんだと知り、驚き。ってことで、絶賛two pointer法を勉強中。
どうやらtwo pointer法もいろんな方があるらしく(貪欲法、尺取り法など)そんなの覚えるのは面倒なので、two　pointer法全部で通用する方法を模索中。

まずtwo pointer法との素敵な出会いは LeetCode 443 - String Compression
問題文：

文字の配列 chars が与えられます。以下のアルゴリズムを使用して圧縮してください：

空の文字列 s から始めます。chars 内の連続する同じ文字のグループごとに：

グループの長さが1の場合、その文字を s に追加します
それ以外の場合、文字の後にグループの長さを追加します
圧縮された文字列 s は別に返すのではなく、入力文字配列 chars に格納する必要があります。

配列の新しい長さを返してください。
入力: chars = ["a","a","b","b","c","c","c"]
出力: 6を返し、入力配列の最初の6文字は ["a","2","b","2","c","3"] になる

説明: 
"aa" → "a2"
"bb" → "b2"  
"ccc" → "c3"
結果: "a2b2c3" の長さは6

解答：

 def function(self, chars: list[str]) -> int:

    write = 0  # 書き込み位置
    read = 0   # 読み取り位置
    
    while read < len(chars):
        current_char = chars[read]
        start = read  # 同じ文字の開始位置
        
        # 同じ文字をスキップして個数を数える
        while read < len(chars) and chars[read] == current_char:
            read += 1
        
        count = read - start  # 同じ文字の個数
        
        # 文字を書き込み
        chars[write] = current_char
        write += 1
        
        # 個数が2以上なら数字も書き込み
        if count > 1:
            count_str = str(count)
            for digit in count_str:
                chars[write] = digit
                write += 1
    
    return write

私の直感的アプローチはwhileを二個重ねて、処理するやり方だったんだが、これだと時間計算量とやらが、O(n^2)になってダメらしく、pointerを配列を左から右の一方向に進ませる(戻ってきたらダメ)だけで答えを出すのが重要らしい。これwriteとreadの動きが分離していてわかりにくいので、初見で出すのは無理でしょう。readは常に右に進み続けるのでそれを軸にして、writeの役割を考えるとわかりやすい。

この先はLeetCodeの類題を解いていくことに。
26,27は同様にread,writeを使いよりシンプル
次に悩んだのは LeetCode 283 - Move Zeroes
問題文：

整数配列numsが与えられる。すべての0を末尾に移動し、
0以外の要素の相対的な順序を保持せよ。
この操作をin-placeで行わなければならない。

Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]

Input: nums = [0]
Output: [0]

解答：

def function(self, nums: list[int]) -> list[int]:
    write = 0  
    read = 0
    while read < len(nums):
        if nums[read] != 0:#  # 0でない場合のみ処理
            if write != read:
                nums[write], nums[read] = nums[read], nums[write]#この時にwriteは一番後ろの0にないといけない
            write += 1 #writeを進める
        # readは常に進める
        read += 1
    return nums

配列要素の入れ替え(スワップ)が出てきたというのと、readの左はソート済みだという点を抑える。

次にわかるわけがなかったのは LeetCode 80 - Remove Duplicates from Sorted Array II

問題：

整数配列numsが昇順でソートされている。重複する要素をin-placeで削除し、
各要素が最大2回まで出現するようにせよ。新しい長さを返せ。

Input: nums = [1,1,1,2,2,3]
Output: 5, nums = [1,1,2,2,3,_]

Input: nums = [0,0,1,1,1,1,2,3,3]  
Output: 7, nums = [0,0,1,1,2,3,3,_,_]

解答：

def function(self, nums: list[int]) -> int:
    if len(nums) <= 2:
        return len(nums)
    
    write = 2  # 最初の2個は必ず保持
    pre_nums = nums
    for read in range(2, len(nums)):  # 3番目から開始
        # write-2位置の要素と比較
        if nums[read] != nums[write - 2]:
            print(f"{nums}")
            nums[write] = nums[read]
            print(f"write: {write}, read: {read}, nums: {nums}")
            print
            write += 1
            
    return write

writeの２に個前を比較するって天才的発想じゃん。思い付くわけねえだろと思った印象。ただ学べることもある。とりあえずreadは常に進めて、その中でどうゆう自分ならどのような操作をするかを考える。
三個連続してるところをピン止めしてそのピンの数字と違うものが来たら代入する、そのあと代入した数字が続いてるなら、二連続まで許して代入し、三個連続になるんだったらそこをピン止めする。ここまで咀嚼できれば、writeの動かし方が思いつくかもしれない。

最後にやったのはLeetCode 11 - Container With Most Water
問題：

整数配列 height が与えられます。この配列には n 本の垂直線が描かれており、i 番目の線の両端点は (i, 0) と (i, height[i]) です。

2本の線を選んで、x軸と一緒に最も多くの水を含むことができる容器を見つけてください。

最大の水の面積を返してください。
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49

解答

def maxArea(self, height: list[int]) -> int:
    left = 0
    right = len(height) - 1
    max_area = 0
    
    while left < right:
        # 現在の面積を計算
        width = right - left
        current_height = min(height[left], height[right])
        area = current_height * width
        
        # 最大面積を更新
        max_area = max(max_area, area)
        
        # 核心: 低い方のポインタを内側に移動
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
            
    return max_area

この問題は、pointerをrigth,leftとして、高さが小さいほうのpointerをright,leftが交差するまで動かすというもの、わたしはread,writeをやりすぎていたせいで無理やりこれで解こうとしたができなかった。max()で面積を更新するというのがわかれば自然と思いつくだろう。
two pointer法には大きく分けて3種類型があるらしい
🟦 型① 尺取り法 条件を満たす区間探索 left/right を動かす 和・種類・連続性
🟩 型② 読み書き法 不要な要素除去 read/write を使う 圧縮・重複除去
🟥 型③ 中央交差 ソート配列で探索 left/right を両端から 2Sum, 最大面積など
それぞれ一問くらいはコード暗記しとこうかなあ