casyup.me@outlook.com

0%

leetcode/SubarraySumEqualsk

Posted on

Subarray Sum Equals k

连续和次数

my solution

问题在于数字是有符号的. 那么如果用单纯的首位前进的方式的话, 就无法得知何时应该首前进, 而何时尾前进.

比如数字: [1, 2, -4], 求和 -1. 当你在 1 看到 2 时, 可能觉得之后的数字都是增加的 然后就不继续了.

(PS: 这里突然看到一个人生哲学, 你知道下一次是失败还是成功, 但是不知道这之后又是什么, 大多数都只看到直接的结果, 而很少看到结果之后的东西. 这是我没放弃这道题的原因 :), 本来没什么好的点子, 按照我的做法, 会留到以后做的, 或许解决近在咫尺了呢?)

所以采用了最简单的方法: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        for (int i = 1; i < nums.size(); ++i)
            nums[i] += nums[i - 1];
        
        int ret = 0;
        for (int i = 0, sub = 0; i < nums.size(); ++i) {
            for (int j = i; j < nums.size(); ++j) {
                if (nums[j] - sub == k) 
                    ++ret;
            }
            sub = nums[i];
        }
        
        return ret;
    }
};

肉眼可见的平方级/2. 虽然通过了, 但效率极低

the best solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int sum=0;
        unordered_map<int,int> h;
        h[0]++;
        int count=0;
        for (int i=0; i < nums.size(); i++) {
            sum += nums[i];
            if ( h.count(sum - k) )
                count += h[sum-k];
            ++h[sum];
        }
        return count;
    }
};

所以说思路啊 = = …

很简单的, 核心是 sum - k, 其含义是符合的已走距离, 比如当前 sum 是 10, 而 k 为 2. 那么所有之前 sum 为 8 的点, , 其距离至当前点的和都可以满足条件. 这也是为什么 0 一开始初始化为 1 的原因. 因为那等同于起点.