Daily 16/03/2024: [525. Contiguous Array](https://leetcode.com/problems/contiguous-array/)

# 1. Tóm tắt đề bài
Cho một mảng nhị phân ```nums```, trả về độ dài tối đa của một mảng con liền kề có số lượng ```0``` và ```1``` bằng nhau.

#### Giới hạn
- $1 \le$ ```nums.length``` $\le 10^5$
- ```nums[i]``` có giá trị ```0``` hoặc ```1```

# 2. Tóm tắt lời giải

#### Phân tích
- Chúng ta có một nhận xét rất thú vị sau, một mảng con liền kề với số lượng ```0``` và ```1``` bằng nhau thì tổng của chúng sẽ là một nửa độ dài mảng đó. Nếu thay ```0``` bằng ```-1``` thì sao? Tổng của chúng chính là ```0```. Bài toán chúng ta có thể quy thành tìm mảng con dài nhất có tổng bằng ```0```.
- Đến đây thì chúng ta có thể dễ dàng giải bằng ```prefix sum```. Chúng ta chỉ cần xét tất cả các điểm mà ```prefix sum``` bằng nhau giả sử là ```i``` và ```j``` thì mảng con từ ```i``` tới ```j``` sẽ có tổng bằng ```0```.
- Vì bài toán là tìm mảng con lớn nhất, nên với mỗi giá trị prefix sum chúng ta chỉ cần lưu index có giá trị đó đầu tiên và xét tiếp các index tiếp theo.
# 3. Lời giải chi tiết

#### Code

class Solution:
    def findMaxLength(self, nums: List[int]) -> int:
        nums = [-1 if x == 0 else x for x in nums]
        has = {}
        has[0] = -1

        sum, ans = 0, 0
        for i, x in enumerate(nums):
            sum += x

            if sum in has:
                ans = max(ans, i - has[sum])
            else:
                has[sum] = i

        return ans

#### Độ phức tạp
$O(nlog(n))$
# 4. Kết luận & gợi ý mở rộng
- Một bài cuối tuần rất nhẹ nhàng.

> Hãy dùng nghị lực và sự kiên trì để đánh bại mọi thứ.

###### #Hashtag: <span style='color: blue'>Prefix Sum, Dictionary, Pointers</span>