leetcode
  • LeetCode Problems
  • Array
    • Array Partition I
    • Toeplitz Matrix
    • Find All Numbers Disappeared in an Array
    • Max Area of Island
    • Move Zeros
    • Two Sum II - Input array is sorted
    • Degree of an Array
    • Image Smoother
    • Positions of Large Groups
    • Missing Number
    • Maximum Product of Three Numbers
    • Min Cost Climbing Stairs
    • Longest Continuous Increasing Subsequence
    • Remove Element
    • Pascal's Triangle
    • Maximum Subarray
    • Largest Number At Least Twice of Others
    • Search Insert Position
    • Plus One
    • Find Pivot Index
    • Pascal's Triangle II
    • Two Sum
    • Maximize Distance to Closest Person
    • Maximum Average Subarray I
    • Remove Duplicates from Sorted Array
    • Magic Squares In Grid
    • Contains Duplicate II
    • Merge Sorted Array
    • Can Place Flowers
    • Shortest Unsorted Continuous Subarray
    • K-diff Pairs in an Array
    • Third Maximum Number
    • Rotate Array
    • Non-decreasing Array
    • Find All Duplicates in an Array
    • Teemo Attacking
    • Beautiful Arrangement II
    • Product of Array Except Self
    • Max Chunks To Make Sorted
    • Subsets
    • Best Time to Buy and Sell Stock with Transaction Fee
    • Combination Sum III
    • Find the Duplicate Number
    • Unique Paths
    • Rotate Image
    • My Calendar I
    • Spiral Matrix II
    • Combination Sum
    • Task Scheduler
    • Valid Triangle Number
    • Minimum Path Sum
    • Number of Subarrays with Bounded Maximum
    • Insert Delete GetRandom O(1)
    • Find Minimum in Rotated Sorted Array
    • Sort Colors
    • Find Peak Element
    • Subarray Sum Equals K
    • Subsets II
    • Maximum Swap
    • Remove Duplicates from Sorted Array II
    • Maximum Length of Repeated Subarray
    • Image Overlap
    • Length of Longest Fibonacci Subsequence
  • Contest
    • Binary Gap
    • Advantage Shuffle
    • Minimum Number of Refueling Stops
    • Reordered Power of 2
  • Dynamic Programming
    • Climbing Stairs
    • Range Sum Query - Immutable
    • Counting Bits
    • Arithmetic Slices
    • Palindromic Substrings
    • Minimum ASCII Delete Sum for Two Strings
    • Maximum Length of Pair Chain
    • Integer Break
    • Shopping Offers
    • Count Numbers with Unique Digits
    • 2 Keys Keyboard
    • Predict the Winner
    • Stone Game
    • Is Subsequence
    • Delete and Earn
    • Longest Palindromic Subsequence
    • Target Sum
    • Unique Binary Search Trees
    • Minimum Path Sum
    • Combination Sum IV
    • Best Time to Buy and Sell Stock with Cooldown
    • Largest Sum of Averages
    • Largest Plus Sign
    • Untitled
  • Invert Binary Tree
  • Intersection of Two Arrays
  • Surface Area of 3D Shapes
  • K Closest Points to Origin
  • Rotting Oranges
  • Smallest Integer Divisible by K
  • Duplicate Zeros
  • DI String Match
  • Implement Queue using Stacks
  • Increasing Order Search Tree
  • Reveal Cards In Increasing Order
  • Reshape the Matrix
  • Partition List
  • Total Hamming Distance
  • Validate Binary Search Tree
  • Decode Ways
  • Construct Binary Tree from Preorder and Inorder Traversal
  • Construct Binary Search Tree from Preorder Traversal
  • Design Circular Queue
  • Network Delay Time
  • Most Frequent Subtree Sum
  • Asteroid Collision
  • Binary Tree Inorder Traversal
  • Check If Word Is Valid After Substitutions
  • Construct Binary Tree from Preorder and Postorder Traversal
  • K-Concatenation Maximum Sum
Powered by GitBook
On this page
  • Description
  • Solutions
  • My solution
  • Optimal solution
  1. Array

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:

  1. The length of the array is in range [1, 20,000].

  2. The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

Solutions

My solution

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        // hash[sum]: a list of i such that sum(nums[0..i]) == sum
        unordered_map<int, vector<int>> hash;
        int sum = 0;
        for(int i = 0; i < n; ++i){
            sum += nums[i];
            hash[sum].push_back(i);
        }
        int count = 0;
        // sum(nums[i..j]), 0 <= i <= j < n, dp[j+1] - dp[i]
        sum = 0;
        for(int i = 0; i < n; ++i){
            auto it = hash.find(sum + k);
            if(it != hash.end()){
                for(int j : it->second){
                    if(j >= i)
                        ++count;
                }
            }
            sum += nums[i];
        }
        return count;
    }
};

Optimal solution

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        // hash[sum]: number of vectors nums[0..j] such that j < i and sum(nums[0..j]) == sum
        unordered_map<int, int> hash;
        hash[0] = 1;
        int n = nums.size(), sum = 0, count = 0;
        for(int i = 0; i < n; ++i){
            sum += nums[i];
            auto it = hash.find(sum - k);
            if(it != hash.end())
                count += it->second;
            ++hash[sum];
        }
        return count;
    }
};
PreviousFind Peak ElementNextSubsets II

Last updated 6 years ago