LeetCode C++ 560. Subaray Sum Equals K【配列/ハッシュテーブル/接頭辞和】中等

Given an array of integers and an integer k k k , you need to find the total number of continuous subarrays whose sum equals to k k k .
Example 1:

Input:nums = [1,1,1], k = 2
Output: 2

Constraints:

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] .

題意:要素とk k kに等しい連続サブ配列の個数を探し出す.
構想1:各サブ配列を検索し、それらの和を計算します.
コードは次のとおりです.時間の制限を超えています.

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int num = 0;
        for (int i = 0; i < nums.size(); ++i) {
            int sum = 0;
            for (int j = i; j < nums.size(); ++j) {
                sum += nums[j];
                if (sum == k) ++num;
            }
        }
        return num;
    }
};

考え方2:O(N)text{O(N)}O(N)まで時間の複雑さを低減するために,考えてみる必要がある.我々の目的は,和kの連続サブ配列の個数を求めることである.区間和をいかに素早く求めるか――接頭辞とsum(nums[i:j]) = sum(nums[:j]) - sum(nums[:i])!しかし、どのように題意と結びついているのでしょうか.我々は普段プレフィックス和を用いているが,連続区間[i, j]の和を求めるために,これをkと仮定すると,sum(nums[:j]) - sum(nums[i:j]) = sum(nums[:j]) - k = sum(nums[:i])という公式が成り立つ.
我々は、遍歴群numsを用いて、最初の要素から現在の要素までの和を計算し、ハッシュテーブルを用いて累積和sumの出現回数を格納する.現在sum(nums[:j])の値があり、前のすべての積算和sum(nums[:i])が同時に記憶されているが、nums[0:j]については、この区間内に和sum(nums[0:j]) - k = sum(nums[:i])のサブ配列が存在する場合、和kのサブ配列が存在することを示し、現在の下付きjより前に連続するサブ配列の和がkである.和kのサブ配列の個数にはsum(nums[:i])ハッシュテーブルでの出現回数を加算する必要がある.
コード:

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int num = 0, sum = 0;
        unordered_map<int, int> dict;
        dict[0] = 1;
        for (int i = 0; i < nums.size(); ++i) { 
        	sum += nums[i];
        	num += dict[sum - k];
	        ++dict[sum];
        }
        return num;
    }
};

効率:

    ：116 ms,     C++       55.37%    
    ：26.5 MB,     C++       20.82%