Leetcode日記

# Two Sum

解説見ながら解きました。
合計がtargetになるようにlistから２つ数字を取って、それらのindexを返す問題です。

### 解法
cur: int (現在の数字)
x: int (xとcurの合計がtargetになるような数字)
d: dict (key: nums[i], value: i)

- for文でnumsを回す
- curとxを求める
- もし、xがdにあったら、
    - i: numsに含まれる、現在の数字（cur）のindex番号
    - d.get(x): numsに含まれる、xのindex番号
- dに要素を追加
    - key: nums[i]
    - value: i


```python
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # cur + x = target
        # x = target - cur
        d = {}
        # key : nums[i] 
        # value : i
        for i in range(len(nums)):
            cur = nums[i]
            x = target - cur
            if x in d:
                return [i, d.get(x)]
            d[nums[i]] = i
```

# Add Two Numbers
解説見ながら解きました。
単方向リストをそれぞれ足していき、足した結果が１０を超える場合は繰り上げする問題です。
[この方の記事](#https://qiita.com/happyisland44/items/ac516aad49809caf74ea)わかりやすいです

### 解法
carry: int (繰り上げ)
val1:　int　（l1の値）
val2:　int　（l2の値）

- while文でl1、l2、carryがなくなるまで回す
- val1、val2に値をそれぞれ代入する（l１、l2に値がない場合は0）
- 合計 sum = val1 + val2 + carry
- carry = (val1 + val2 + carry) / 10
- sumの10で割ったあまりの値を持つ新しいノードを作成し、カレントノードのnextに設定し、カレントノードをnextに進める
- l1、l2を次の値に進める

```python
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        # plus 1 to next digit 
        carry = 0
        dummy_head = ListNode(0)
        current = dummy_head

        while l1 or l2 or carry:
            val1 = l1.val if l1 else 0
            val2 = l2.val if l2 else 0
            current.next = ListNode((val1 + val2 + carry) % 10)
            current = current.next
            
            if (val1 + val2 + carry) >= 10:
                carry = 1
            else:
                carry = 0
            
            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None

        return dummy_head.next
```


# Longest Substring Without Repeating Characters

### 解法１ Brute Force
TLEになります
```python
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        result = 0
        for i in range(len(s)):
            for j in range(i,len(s)):
                # インデックスがi番目からj番目までの文字列sが、重複していない場合
                if self.check(s, i, j):
                    #　今までの最大値resultと、インデックスがi番目からj番目までの文字数（j-i+1)を比較し、大きい方をresultに代入
                    result = max(result, j - i + 1)
        return result
        
    # インデックスがstart番目からend番目までの文字列sが、重複していないかどうか？
    # "abc" -> True
    # "aab" -> False
    def check(self, s: str, start: int, end: int):
        list_s = []
        for i in range(start, end+1):
            if s[i] not in list_s:
                list_s.append(s[i])
            else:
                return False
        return True
```

### 解法2 Sliding Window

文字列sが与えられた時、重複を許さない、かつ連続した文字列の数の最大値を求める問題です

chars: Conter（Sliding Window内で何回その文字が出現したか、カウントする）
left:　int（Sliding Windowの範囲を狭める）
right:　int（Sliding Windowの範囲を拡大する）
res: int(重複を許さない、連続した文字列の数の最大値)
r: str(文字列sのright番目の文字s[right])
l: str(文字列sのleft番目の文字s[left])


1. rightは文字列sの長さを超えずに、Sliding Windowの範囲を拡大する
2. Sliding Windowの範囲に何回その文字が出現したか、カウントするために、文字列sのright番目の文字rをcharsに追加する
    - 文字列sのright番目の文字s[right]を文字rに代入
    - 文字rをcharsに登録する
3. もし文字rの出現回数が1回以上だったら、Sliding Windowの範囲を狭める
    -  文字列sのleft番目の文字s[left]を文字lに代入
    -  Sliding Windowの範囲を狭めたので、出現回数をカウントしているcharsから狭めた文字のカウントを１減らす
    -  leftを１つスライドさせる
4. 現在のSliding Windowの範囲に重複する文字は無くなったので、Sliding Windowの範囲の最大値を求める
5. rightを１つスライドさせる

```python
from collections import Counter
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # we need to declare a direct access table to record how many times each character appears in the sliding window
        # So we declare the table as an int array, 
        # and all the characters can be encoded into integers
        
        chars = Counter()
        #left :contract the window
        #right :expand the window
        left = 0
        right = 0
        
        res = 0
        # slide the window
        while right < len(s):
        
            # obtain the character at the right boundary
            # we can add one more time for this character's occurence
            # we can keep extending the window
            r = s[right]
            chars[r] += 1

            # Before extending the window, we shold firstly consider contracting the window
            # So if the character at the right boundary appears more than once,
            # we need to keep contracting the window
            # To contract the window, we should get the character at the left boundary,
            # and to reduce it's occurrence
            # Then move forward the left pointer
            while chars[r] > 1:
                l = s[left]
                chars[l] -=1
                left += 1
        
            # after contracting the window
            # we can make sure that there is no duplicate character in the current window
            res = max(res, right - left + 1)
            right += 1

        return res
```
### 解法3 Sliding Window Optimized

文字列sが与えられた時、重複を許さない、かつ連続した文字列の数の最大値を求める問題です

mp: dict（key: 文字、　value: 文字の現在のindex+1）
i:　int（Sliding Windowの範囲を狭める）
j:　int（Sliding Windowの範囲を拡大する）
res: int(重複を許さない、連続した文字列の数の最大値)
n: int(文字列sの長さ)

r: str(文字列sのright番目の文字s[right])
l: str(文字列sのleft番目の文字s[left])


1. jは文字列sの長さnを超えずに、Sliding Windowの範囲を拡大する
2. もしs[j]が既に出現されていたら、sliding windowの範囲を重複しない範囲に狭める
    - iを重複した文字s[j]の前回のindex+1と現在のiを比較し、iを文字列が重複しないようにスライドさせる
3. 現在のSliding Windowの範囲に重複する文字は無くなったので、Sliding Windowの範囲の最大値を求める
4. mpにkey: 文字s[j], value: 文字s[j]の現在のindex+1を登録
    - ＋１する理由---> 次に文字s[j]が重複した際に、iをmp[s[j]]に移動することで、重複しないようにsliding windowの範囲を狭めることができる

```python
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        n = len(s)
        res = 0
        # mp stores the current index + 1 
        # key : 文字
        # value : 文字の現在のindex + 1
        mp = {}
        # i: contract the window
        # j: extend the window
        i = 0
        for j in range(n):
            # s[j]が既に出現されていたら
            if s[j] in mp:
                # sliding window の幅を狭める
                # iをmp[s[j]]と現在のiを比較し、大きい方にiをスライドさせる
                # mp[s[j]]　：　重複した文字s[j]の前回のindex+1
                # +1する理由は重複しないように、重複した文字s[j]の次の文字を指すindexを指定するため
                i = max(mp[s[j]], i)
            res = max(res, j - i + 1)
            # mp に
                # key: 文字s[j], value: 文字s[j]の現在のindex　+ 1
            # を登録
            mp[s[j]] = j + 1
        return res
```