LeetCode 560 Subarray Sum Equals K

标签: 数组类题目 LeetCode 发布于:2022-02-12 12:02:07 编辑于:2022-02-12 16:33:24 浏览量:989

概述

https://leetcode.com/problems/subarray-sum-equals-k/

滑动窗口法(无法处理有负值的情况)

从左向右遍历数组,当下一个元素加入窗口后发现值超出,就抛弃掉最左边的元素,然后继续。

历次 WA 的原因:

  1. 没有对 l 和 r 的大小关系做检查,导致 case k == 0,nums = [1] 失败;
  2. 没有想到输入是可以为负数,负值的出现使得合法的子窗口可以嵌套,我们原本的思路是错误的。
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int count = 0;
        int l = 0;  // the case the first element is bigger than k
        int sum = 0;
        for (int r = 0; r < nums.size(); r ++) {
            sum += nums[r];
            if (sum == k) {
                count ++;
            } else if (sum < k) {
                continue;
            } else {  // sum > k
                while (sum > k) {
                    sum -= nums[l];
                    l ++;
                }
                if (sum == k && l <= r) count ++;  // the case k == 0 && nums = [1]
            }
        }
        return count;
    }
};

起始点结束点暴力遍历法

双层 for 循环遍历所有可能的起始点和结束点。

O(n^2) 的时间复杂度。

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

TLE 了。

中间节点暴力遍历法

中间节点可以是一个,也可以是两个。

由于这次有两个嵌套 for 循环,因此这次更早 TLE 了。

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int count = 0;
        for (int m = 0; m < nums.size(); m ++) {
            int sum = nums[m];
            if (sum == k) count ++;
            for (int d = 1; m - d >= 0 && m + d < nums.size(); d ++) {
                sum += nums[m - d] + nums[m + d];
                if (sum == k) count ++;
            }
        }
        for (int m = 0; m < nums.size() - 1; m ++) {
            int sum = nums[m] + nums[m + 1];
            if (sum == k) count ++;
            for (int d = 1; m - d >= 0 && m + 1 + d < nums.size(); d ++) {
                sum += nums[m - d] + nums[m + 1 + d];
                if (sum == k) count ++;
            }
        }        
        return count;
    }
};

前缀和数组

https://labuladong.gitee.io/algo/2/21/56/

构造一个前缀和矩阵

我们没有必要构造前缀和矩阵啊喂,前缀和向量足够了。

注意,实现的时候 sums[i] 里存的值不包括 nums[i],务必注意 i 与 j 的范围。

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

然后我们就再次 TLE 了,时间复杂度也依然是 O(n^2)。

我们可以用一个 map 记录 sums[i] + k 的出现次数,这样就可以一次遍历解决问题。

注意里面 count 可不是加 1 哦,而是直接加上历史出现个数。

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        vector<int> sums(nums.size() + 1, 0);
        for (int i = 0; i < nums.size(); i ++) {
            sums[i + 1] = sums[i] + nums[i];
        }
        int count = 0;
        unordered_map<int, int> m;
        for (int i = 0; i <= nums.size(); i ++) {
            if (m.count(sums[i]) != 0) {
                count += m[sums[i]];
            }
            m[sums[i] + k] += 1;
        }
        return count;
    }
};

更进一步地,我们可以合并两个 for 循环:

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int count = 0;
        unordered_map<int, int> m;
        for (int i = 0; i <= nums.size(); i ++) {
            if (i < nums.size()) sums[i + 1] = sums[i] + nums[i];
            if (m.count(sums[i]) != 0) {
                count += m[sums[i]];
            }
            m[sums[i] + k] += 1;
        }
        return count;
    }
};

更进一步地,我们可以取代 sums 数组,此时时间复杂度 O(n),空间复杂度 O(n)(map 省不掉):

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        vector<int> sums(nums.size() + 1, 0);
        int count = 0;
        unordered_map<int, int> m;
        int currentSum = 0, nextSum = 0;
        for (int i = 0; i <= nums.size(); i ++) {
            currentSum = nextSum;
            if (i < nums.size()) nextSum = currentSum + nums[i];
            if (m.count(currentSum) != 0) {
                count += m[currentSum];
            }
            m[currentSum + k] += 1;
        }
        return count;
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/