Add 523_Continuous_Subarray_Sum.py (qiyuangong#68)

LONGNEW · web-flow · commit fefe70c3ce3f · 2022-10-30T11:24:08.000+08:00
* Add 523_Continuous_Subarray_Sum.py Contributed by @LONGNEW
diff --git a/README.md b/README.md
@@ -166,6 +166,7 @@ I'm currently working on [Analytics-Zoo](https://github.com/intel-analytics/anal
 | 482 | [License Key Formatting](https://leetcode.com/problems/license-key-formatting/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/482_License_Key_Formatting.py) [Java](https://github.com/qiyuangong/leetcode/blob/master/java/482_License_Key_Formatting.java) | String processing, lower and len % K, O(n) and O(n) |
 | 485 | [Max Consecutive Ones](https://leetcode.com/problems/max-consecutive-ones/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/485_Max_Consecutive_Ones.py) [Java](https://github.com/qiyuangong/leetcode/blob/master/java/485_Max_Consecutive_Ones.java) | Add one when encounter 1, set to 0 when encounter 0, O(n) and O(1) |
 | 509 | [Fibonacci Number](https://leetcode.com/problems/fibonacci-number/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/509_Fibonacci_Number.py) [Java](https://github.com/qiyuangong/leetcode/blob/master/java/509_Fibonacci_Number.java) | 1. Recursive, O(n) <br>2. DP with memo, O(n). Note that N<=30, which means that we can keep a memo from 0 to 30. |
+| 523 | [Continuous Subarray Sum](https://leetcode.com/problems/continuous-subarray-sum/description/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/523_Continuous_Subarray_Sum.py) | O(n) solution using dict() |
 | 538 | [Convert BST to Greater Tree](https://leetcode.com/problems/convert-bst-to-greater-tree/description/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/538_Convert_BST_to_Greater_Tree.py) [Java](https://github.com/qiyuangong/leetcode/blob/master/java/538_Convert_BST_to_Greater_Tree.java) | Right first DFS with a variable recording sum of node.val and right.val. 1. Recursive.<br>2. Stack 3. Reverse Morris In-order Traversal |
 | 541 | [Reverse String II](https://leetcode.com/problems/reverse-string-ii/solution/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/541_Reverse_String_II.py) [Java](https://github.com/qiyuangong/leetcode/blob/master/java/541_Reverse_String_II.java) | Handle each 2k until reaching end, On(n) and O(n) |
 | 543 | [Diameter of Binary Tree](https://leetcode.com/problems/diameter-of-binary-tree/description/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/543_Diameter_of_Binary_Tree.py) [Java](https://github.com/qiyuangong/leetcode/blob/master/java/543_Diameter_of_Binary_Tree.java) | DFS with O(1) for max answer |
diff --git a/python/523_Continuous_Subarray_Sum.py b/python/523_Continuous_Subarray_Sum.py
@@ -0,0 +1,20 @@
+class Solution:
+    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
+        # remeainders[0] = 0 is for when x == 0
+        remainders = dict()
+        remainders[0] = 0
+        pre_sum = 0
+
+        for idx, item in enumerate(nums):
+            pre_sum += item
+            remaind = pre_sum % k
+
+            # remainder doesnt exist then it has to be init
+            # if it exists, then check the prev one has the same remainder
+            if remaind not in remainders:
+                remainders[remaind] = idx + 1
+            elif remainders[remaind] < idx:
+                return True
+
+        return False
+    
