560. Subarray sum equals k

發表於 | 分類於

problem

找出連續子陣列，其總和為k 的數量

solution

  • hash table 統計連續子陣列總和及相應數量
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    class Solution {
    public:
        int subarraySum(vector<int>& nums, int k) {
            //      1   1   1
            //sum   1   2   3
            // dict = {{0,1}}
            // i = 0, dict = {{0,1}, {1,1}};
            // i = 1, dict = {{0,1},{1,1},{2,1}};
            // i = 2, dict = {{0,1},{1,1},{2,1}, {3,1}};
            // hash table 代表子陣列總和與其次數
            int count = 0, n = nums.size(), sum=0;
            unordered_map<int,int> sub;
            sub[0] = 1;
            for(int i=0;i<n;++i){
                sum+=nums[i];
                if(sub.find(sum-k)!=sub.end()) count+=sub[sum-k];
                sub[sum]++;
            }
            return count;
            
        }
    };

    analyze

  • time complexity O(n)
  • space complexity O(n)