LeetCode: TwoSum, BalancedStringSplit

TwoSum

https://leetcode.com/problems/two-sum/

Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

• 与えられた nums から数を二つ選んだ和 target の値に一致するような index を配列で返す
• 2つの数の和を表にすると以下のような感じ
  • つまり Pfor i in range(len(nums)); for j in range(i+1, range(len(nums)));` のループを回してあげればよさそう

|    | 11 | 7  | 2  | 15 |
|:--:|:--:|:--:|:--:|:--:|
| 11 | x  | 18  | 13 | 26 | 
| 7  | -  | x   | 9  | 22 |
| 2  | -  | -   | x  | 17 |
| 15 | -  | -   | -  | x  |

• 上記の和の表的な考え方をコードに落とし込むと以下のようになる
  • が n * (n -1) ~ O(n^2) の計算量となる

# 5340 ms
# 14.8 MB

from typing import List


class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        for i in range(n):
            for j in range(i + 1, n):
                if nums[i] + nums[j] == target:
                    return [i, j]
        return []

戦略を変えて一回の走査で解けるような方法を考える。

たとえば n_i = [11, 2, 9, 7 , 15] という配列から和が target = 9 となる組み合わせを見つけたいときを考える

• i = 0: 11 との和が 9 になるのは -2
• i = 1: 2 との和が 9 になるのは 7
• i = 2: 9 との和が 9 になるのは 0
• i = 3: 7 は以前 i = 1 にちょうど欲しかった数
  • この欲しかった数とインデックスをハッシュテーブルに突っ込んでおけば、インデックスへ O(1) でアクセスでき、(1, 3) という回答を導き出せる

この方法を使えば、O(n) で問題が解ける。コードに落とし込むと以下のような形となる。

# 44 ms
# 14.2 MB

from typing import List


class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        d = {}
        for j in range(len(nums)):
            i = d.get(nums[j], None)
            if i is not None:
                return [i, j]
            d[target - nums[j]] = j

BalancedStringSplit

Split a String in Balanced Strings – LeetCode

Balanced strings are those who have equal quantity of ‘L’ and ‘R’ characters.
Given a balanced string s split it in the maximum amount of balanced strings.
Return the maximum amount of splitted balanced strings.

• 問題の名前が解法のネタバレっぽい
• L と R がバランスしたら、カウントアップ
• カウンタとバランスカウンタは必要に思える

class Solution:
    def balancedStringSplit(self, s: str) -> int:
        balance, total = 0, 0
        for x in s:
            balance = balance + 1 if x == 'L' else balance - 1
            if balance == 0:
                total += 1
        return total