560. Subarray Sum Equals K

Medium (Trung bình) C++ Python 🔗 Xem trên LeetCode

📋 Đề Bài

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

🧠 Thuật Toán & Kỹ Thuật

Hash Table (Bảng băm)Prefix Sum (Tổng tiền tố)
⏱️ Thời gian O(n²)
💾 Không gian O(n)

💻 Lời Giải

C++ 0560-subarray-sum-equals-k.cpp 
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> pref;
        pref[0] = 1;
        int sum = 0, ans = 0;
        
        for (int num : nums) {
            sum += num;
            ans += pref[sum - k];
            pref[sum]++;
        }
        
        return ans;
    }
};
Python 0560-subarray-sum-equals-k.py 
class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        hashMap = defaultdict(int)
        total = 0
        hashMap[0] = 1
        ans = 0
        
        # pref[i] - prefix[j] == k
        
        for num in nums:
            total += num
            ans += hashMap[total - k]
            hashMap[total] += 1
            
        return ans