[LeetCode] 560. Subarray Sum Equals K 子数组和为K
2023-09-27 14:28:37 时间
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].
解法1: Brute force. 用两丛循环i, j,计算sum[i, j],如果等于K则记录结果。T: O(n^2) S: O(1), 会TLE
解法2:Hashtable,基于公式 sum(i - j) = sum(0, j) - sum(0, i), 每循环一次都把数字累加到sum, 并用一个哈希表记录,key是sum, value是出现过的次数。当满足sum - K在哈希表中时,说明去掉之前那段和的数后剩下的数字和等于K, 满足条件,把记录的次数累加到结果(因为有多种组合可能)。T: O(n), S: O(n).
参考: https://discuss.leetcode.com/topic/87850/java-solution-presum-hashmap
Java:
public class _560 { public int subarraySum(int[] nums, int k) { Map<Integer, Integer> preSum = new HashMap(); int sum = 0; int result = 0; preSum.put(0, 1); for (int i = 0; i < nums.length; i++) { sum += nums[i]; if (preSum.containsKey(sum - k)) { result += preSum.get(sum - k); } preSum.put(sum, preSum.getOrDefault(sum, 0) + 1); } return result; } }
Python:
class Solution(object): def subarraySum(self, nums, k): """ :type nums: List[int] :type k: int :rtype: int """ ans = sums = 0 cnt = collections.Counter() for num in nums: cnt[sums] += 1 sums += num ans += cnt[sums - k] return ans
Python:
def subarraySum(self, nums, k): count, cur, res = {0: 1}, 0, 0 for v in nums: cur += v res += count.get(cur - k, 0) count[cur] = count.get(cur, 0) + 1 return res
Python: wo
class Solution(object): def subarraySum(self, nums, k): """ :type nums: List[int] :type k: int :rtype: int """ return res res, sums = 0, 0 lookup = collections.Counter() lookup[0] = 1 # important for num in nums: sums += num if lookup[sums - k] > 0: res += lookup[sums - k] lookup[sums] += 1 return res
Python: TLE
class Solution(object): def subarraySum(self, nums, k): """ :type nums: List[int] :type k: int :rtype: int """ res = 0 for i in xrange(len(nums)): sum = 0 for j in xrange(i, len(nums)): sum += nums[j] if sum == k: res += 1 return res
C++:
class Solution { public: int subarraySum(vector<int>& nums, int k) { int res = 0, n = nums.size(); for (int i = 0; i < n; ++i) { int sum = nums[i]; if (sum == k) ++res; for (int j = i + 1; j < n; ++j) { sum += nums[j]; if (sum == k) ++res; } } return res; } };
C++:
class Solution { public: int subarraySum(vector<int>& nums, int k) { int res = 0, sum = 0, n = nums.size(); unordered_map<int, int> m{{0, 1}}; for (int i = 0; i < n; ++i) { sum += nums[i]; res += m[sum - k]; ++m[sum]; } return res; } };
All LeetCode Questions List 题目汇总
相关文章
- 【LeetCode】搜索旋转排序数组 [M](二分)
- 【LeetCode】有效的数独 [M](模拟)
- 【LeetCode】最大间距 [H](基数排序)
- 【LeetCode】监控二叉树 [H](二叉树)
- [LeetCOde][Java] Best Time to Buy and Sell Stock III
- LeetCode_前缀和_哈希表_中等_525.连续数组
- LeetCode_滑动窗口_简单_643.子数组最大平均数 I
- LeetCode_二分搜索_中等_81.搜索旋转排序数组 II
- LeetCode·2289. 使数组按非递减顺序排列·单调栈
- LeetCode·每日一题·862.和至少为 K 的最短子数组·队列+前缀和
- LeetCode·每日一题·1460.通过翻转子数组使两个数组相等·哈希表
- LeetCode·每日一题·1331.数组序号转换·离散化
- leetcode面试题16.24-在无序数组中所有发现和为sum的数对
- [LeetCode] 325. Maximum Size Subarray Sum Equals k 和等于k的最长子数组
- [LeetCode] 384. Shuffle an Array 数组洗牌
- [LeetCode] 529. Minesweeper 扫雷
- [LeetCode] 689. Maximum Sum of 3 Non-Overlapping Subarrays 三个非重叠子数组的最大和
- [LeetCode] 209. Minimum Size Subarray Sum 最短子数组之和
- [LeetCode] 211. Add and Search Word - Data structure design 添加和查找单词-数据结构设计
- [LeetCode] 275. H-Index II H指数 II
- [LeetCode] 557. Reverse Words in a String III 翻转字符串中的单词 III
- [LeetCode] 125. Valid Palindrome 验证回文字符串
- leetcode 70 爬楼梯
- leetcode 349 两个数组的交集