Daily 08/06/2024: [523. Continuous Subarray Sum](https://leetcode.com/problems/continuous-subarray-sum/)

# 1. Tóm tắt đề bài

- Cho một mảng số nguyên ```nums``` và một số nguyên ```k```, trả về ```true``` nếu ```nums``` có **mảng con tốt** hoặc ```false``` nếu ngược lại .
- **Một mảng con tốt** là một mảng con trong đó:
- Chiều dài của nó ít nhất là 2 , và
- Tổng các phần tử của mảng con là bội số của k.
- **Lưu ý** rằng:
- Mảng con là phần liền kề của mảng.
- Một số nguyên ```x``` là bội số của ```k``` nếu tồn tại một số nguyên ```n``` sao cho ```x = n * k```. ```0``` luôn là bội số của ```k```.

#### Giới hạn
- $1 \le$ ```nums.length``` $\le 10^5$
- $1 \le$ ```nums[i]``` $\le 10^9$
- $0 \le$ ```sum(nums[i])``` $\le 2^{31} - 1$
- $1 \le$ ```k``` $\le 2^{31} - 1$

# 2. Tóm tắt lời giải
#### Phân tích
- Với hướng tiếp cận đầu tiên là chạy trâu thì chúng ta đơn giản là xét hết các khoảng xong tính tổng từng khoảng. Độ phức tạp là $O(n^3)$.
- Cải tiến khi chúng ta dùng prefix sum thì sẽ cải tiến xuống $O(n^2)$. Với những bạn mới thì có thể tham khảo ở đây [https://wiki.vnoi.info/algo/data-structures/prefix-sum-and-difference-array.md].
- Tiếp đến thì chúng ta sẽ phân tích là tổng chia hết cho ```k```. Thế thì chúng chỉ quan tâm tới số dư của nó chia ```k``` bằng 0 là được. Vậy thì ý tưởng cải tiến đơn giản hơn là kiểm tra số dư đó đã xuất hiện trong ```prefix sum``` chưa. Giả sử có ```prefix[l - 1]``` và ```prefix[r]``` cùng số dư thì theo tính chất cơ bản ```prefix[r] - prefix[l - 1]``` sẽ chia hết cho ```k```. Hay tổng các phần tử thừ l tới ```r``` sẽ chia hết cho ```k``` và trả về ```true```.
# 3. Lời giải chi tiết
#### Thuật toán
- Sử dụng Hash Table tùy theo ngôn ngữ bạn đọc sử dụng.
#### Code

public class Solution {
    public bool CheckSubarraySum(int[] nums, int k) {
        int prevSum = nums[0] % k;
        int currSum = 0;
        HashSet<int> prefixSum = new HashSet<int>();

        for (int i = 1; i < nums.Length; i++)
        {
            currSum = (prevSum + nums[i]) % k;
            
            if(currSum % k == 0 || prefixSum.Contains(currSum))
                return true;

            if(!prefixSum.Contains(prevSum))
                prefixSum.Add(prevSum);
                
            prevSum = currSum;
        }
        return false;
    }
}

#### Độ phức tạp
$O(n)$.
# 4. Kết luận & gợi ý mở rộng
- Một bài cuối tuần khá 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'>Brute Force, Hash Table</span>