原创 Leetcode新手学习之路--Hash+前缀和_前缀和 hash leetcode

560. 和为K的子数组 解法思路
     创建一个map，key为前缀和，value为出现的次数；
     （1）边遍历边计算前缀和pre；
     （2）判断本次前缀和是否为k，如果是则+1;
     （3）判断当前map中是否存在pre-k，如果存在则count加上对应的value；
     （4）注意：最后才将当前pre更新只map中；否则碰到k为0时总是会多1！
     hash查找：mp.find(pre - k) != mp.end()

方法1：
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> mp;
        int pre = 0;
        int cnt = 0;
        vector<int> preSum(nums.size() + 1);
        preSum[0] = 0; // key1：包含0个元素（不选取任何元素）时和为0
        mp[0] = 1; // key2：和为0的个数（不选取任何元素）至少有1个
        for (int i = 1; i <= nums.size(); i++) {
            preSum[i] += nums[i - 1] + preSum[i - 1];
            if (mp.find(preSum[i] - k) != mp.end()) {
                cnt += mp[preSum[i] - k];
            }
            if (mp.find(preSum[i]) != mp.end()) {
                mp[preSum[i]]++;
            } else {
                mp[preSum[i]] = 1;
            }
        }
        return cnt;
    }
};
方法2：
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> mp;
        int pre = 0;
        int cnt = 0;
        for (int i = 0; i < nums.size(); i++) {
            pre += nums[i];
            // check itself
            if (pre == k) {
                cnt++;
            }
            // check before: check "pre - k" whether exist
            if (mp.find(pre - k) != mp.end()) {
                cnt += mp[pre - k];
            }
            // add "pre" to map
            if (mp.find(pre) != mp.end()) {
                mp[pre]++;
            } else {
                mp[pre] = 1;
            }
        }
        return cnt;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

523. 连续的子数组和
     给定一个包含非负数的数组和一个目标整数 k，编写一个函数来判断该数组是否含有连续的子数组，其大小至少为 2，总和为 k 的倍数，即总和为 n*k，其中 n 也是一个整数。
     思路1：暴力求解法，注意k要分0和非0的情况；

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        if (nums.size() < 2) {
            return false;
        }
        vector<int> pres(nums.size(), 0);
        int pre = 0;
        for (int i = 0; i < nums.size(); i++) {
            pre += nums[i];
            pres[i] = pre;
        }
        for (int i = 0; i < nums.size(); i++) {
            for (int j = i + 1; j < nums.size(); j++) { // key1, j = i + 1
                if (k == 0) { // key2
                    if (pres[j] == 0) {
                        return true;
                    }
                    if ((pres[j] - pres[i] == 0) && (j - i >= 2)) { // key3
                        return true;
                    }
                } else {
                    if (pres[j] % k == 0) {
                        return true;
                    }
                    if (((pres[j] - pres[i]) % k) == 0 && (j - i >= 2)) { // key3
                        return true;
                    }
                }
            }
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

思路2：
Sum[i, j] = preSum[i] - preSum[j - 1]
目标：(preSum[i] - preSum[j - 1] % k) == 0 等价于 (preSum[i] % k ) == (preSum[j - 1] % k)
另外，由于i > j所以i - (j - 1) >= 2，这个是索引下标的条件；

用hash表保存余数和对应的索引下标！！！

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        if (nums.size() < 2) {
            return false;
        }
        int N = nums.size();
        if (k == 0) {
            for (int i = 1; i < N; i++) {
                if (nums[i] == 0 && nums[i] == nums[i - 1]) {
                    return true;
                }
            }
            return false;
        }
        unordered_map<int, vector<int>> mp; // 余数，出现的索引
        mp[0].push_back(0); // key1, 默认在数组前面添加一个0元素
        int sum = 0;
        for (int i = 1; i <= N; i++) { // 注意索引要从1开始遍历，0已结被默认添加了
            if (nums[i - 1] < 0) {
                nums[i - 1] = k - (abs(nums[i - 1]) % k);
            }
            sum += nums[i - 1];
            int res = sum % k;
            if (mp.find(res) != mp.end()) {
                for (auto it : mp[res]) {
                    if (i - it >= 2) { // key2
                        return true;
                    }
                }
            }
            mp[res].push_back(i);
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

974. 和可被 K 整除的子数组
     给定一个整数数组 A，返回其中元素之和可被 K 整除的（连续、非空）子数组的数目。
     提示：
     1 <= A.length <= 30000
     -10000 <= A[i] <= 10000
     2 <= K <= 10000

方法1：暴力算法，会超时

class Solution {
public:
    int subarraysDivByK(vector<int>& A, int K) {
        if (A.size() == 0) {
            return 0;
        }
        vector<int> pres(A.size() + 1);
        for (int i = 1; i <= A.size(); i++) {
            pres[i] = pres[i - 1] + A[i - 1];
        }
        int count = 0;
        for (int i = 0; i <= A.size(); i++) {
            for (int j = i + 1; j <= A.size(); j++) {
                if ((pres[j] - pres[i]) % K == 0) {
                    count++;
                }
            }
        }
        return count;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

方法2 思路：通过判断两个位置的余数是否相等，从而判断他们的子区间的和是否为K的倍数。[523. 连续的子数组和]更简单一点，只要找出一个即可。
本题将负数进行同余预处理。如给出：[2,-2,2,-4]，K=6。同余处理之后得到[2,4,2,2]，K=6，求余数之后为[0,2,0,2,4] （第一个0是做前缀和时总是会添加的数）, 余数相等的有两对，答案是2.

class Solution {
public:
    int subarraysDivByK(vector<int>& A, int K) {
        if (A.size() == 0) {
            return 0;
        }
        unordered_map<int, int> mp; // key是余数，value是个数
        mp[0] = 1; // 对于前缀和相当于在数组头插入了个0元素
        int sum = 0;
        int count = 0;
        for (int i = 0; i < A.size(); i++) {
            A[i] = (A[i] < 0) ? (K - abs(A[i]) % K) : A[i]; // 需要做同余处理，否则会漏掉一部分组合
            sum += A[i];
            int res = sum % K;
            if (mp.find(res) != mp.end()) {
                count += mp[res];
                mp[res]++;
            } else {
                mp[res] = 1;
            }
        }
        return count;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24