560. Subarray Sum Equals K

nullskill · nullskill · commit bcc261bb7503 · 2023-07-30T18:42:20.000+03:00
diff --git a/lib/src/medium/560.subarray_sum_equals_k/main.dart b/lib/src/medium/560.subarray_sum_equals_k/main.dart
@@ -0,0 +1,33 @@
+/// This function has a time complexity of `O(n)`,
+/// where `n` is the length of `nums`. This is because
+/// the function iterates through nums once and
+/// performs constant time operations on each element.
+/// The function also uses a map to store the prefix sum,
+/// which has a space complexity of `O(n)` in the worst case,
+/// where `n` is the length of `nums`.
+
+class Solution {
+  int subarraySum(List<int> nums, int k) {
+    int count = 0;
+    int sum = 0;
+    Map<int, int> prefixSum = {0: 1};
+
+    for (int i = 0; i < nums.length; i++) {
+      sum += nums[i];
+      if (prefixSum.containsKey(sum - k)) {
+        count += prefixSum[sum - k]!;
+      }
+      prefixSum[sum] = (prefixSum[sum] ?? 0) + 1;
+    }
+
+    return count;
+  }
+}
+
+void main(List<String> args) {
+  print(Solution().subarraySum([-1, -1, 1], 0));
+  print(Solution().subarraySum([1, 2, 5, 3, 4], 6));
+  print(Solution().subarraySum([1, 1, 1], 2));
+  print(Solution().subarraySum([1], 1));
+  print(Solution().subarraySum([-1, 2, -1, -2, -3], -3));
+}
diff --git a/lib/src/medium/560.subarray_sum_equals_k/problem.txt b/lib/src/medium/560.subarray_sum_equals_k/problem.txt
@@ -0,0 +1,24 @@
+560. Subarray Sum Equals K
+https://leetcode.com/problems/subarray-sum-equals-k/
+
+Given an array of integers nums and an integer k, 
+return the total number of subarrays whose sum equals to k.
+A subarray is a contiguous non-empty sequence of elements within an array.
+ 
+
+Example 1:
+
+Input: nums = [1,1,1], k = 2
+Output: 2
+
+Example 2:
+
+Input: nums = [1,2,3], k = 3
+Output: 2
+ 
+
+Constraints:
+
+1 <= nums.length <= 2 * 104
+-1000 <= nums[i] <= 1000
+-107 <= k <= 107
