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].

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

# 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 となる組み合わせを見つけたいときを考える

この方法を使えば、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.

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