Problem
题目大意：给你一个数组，问有多少子数组的和为k。
https://leetcode.com/problems/subarray-sum-equals-k/description/
Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.
Example 1:
Input:nums = [1,1,1], k = 2 Output: 2
Note:
- The length of the array is in range [1, 20,000].
- The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].
Solution -1: Brute Force
For every pair of i,j, check sum(nums[i:j]) in O(j-i) = O(n)
Time complexity: O(n^3) TLE
Space complexity: O(1)
Solution 0: Brute Force + Prefix sun
Precompute the prefix sum and check sum of nums[i:j] in O(1)
Time complexity: O(n^2)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// Author: Huahua // Running time: 490 ms class Solution { public: int subarraySum(vector<int>& nums, int k) { const int n = nums.size(); vector<int> sums(n + 1, 0); for (int i = 1; i <= n; ++i) sums[i] = sums[i - 1] + nums[i - 1]; int ans = 0; for (int i = 0; i < n; ++i) for (int j = i; j < n; ++j) if (sums[j + 1] - sums[i] == k) ++ans; return ans; } }; |
Solution 1: Running Prefix sum
Keep tracking the prefix sums and their counts.
s -> count: how many arrays nums[0:j] (j < i) that has sum of s
cur_sum = sum(nums[0:i])
check how many arrays nums[0:j] (j < i) that has sum (cur_sum – k)
then there are the same number of arrays nums[j+1: i] that have sum k.
Time complexity: O(n)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// Author: Huahua // Running time: 36 ms class Solution { public: int subarraySum(vector<int>& nums, int k) { if (nums.empty()) return 0; unordered_map<int, int> counts{{0,1}}; int cur_sum = 0; int ans = 0; for (const int num : nums) { cur_sum += num; ans += counts[cur_sum - k]; ++counts[cur_sum]; } return ans; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
Be First to Comment