560-和为K的子数组

LeetCode 560. Subarray Sum Equals K

LeetCode-560

Given an array of integers nums and an integer k, return the total number of continuous subarrays whose sum equals to k.

Example 1:

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

method：前缀和

需要满足的条件是prefix[j] - prefix[i-1] = k，转换为prefix[i-1] = prefix[j] - k，所以以j结尾的子数组，如果已经存在一个前缀和prefix[i-1]，其值为prefix[j]-k，那就说明这个子数组[i,j]满足累加为k，所以用一个哈希表来存储数组的前缀和

int subarraySum(vector<int>& nums, int k) {
    unordered_map<int, int> hash;
    hash[0] = 1;
    int res = 0;
    int pre = 0;
    for (int i = 0; i < nums.size(); i++) {
        pre += nums[i]; // 到当前节点的前缀和
        res += hash[pre - k];   // 1、存在就累加
        hash[pre]++;    // 2、前缀和存入哈希表中，顺序不能反
    }
    return res;
}

---

LeetCode 325. 和等于k的最长子数组长度

给定一个数组 nums 和一个目标值 k，找到和等于 k 的最长连续子数组长度。如果不存在任意一个符合要求的子数组，则返回 0。

示例 1:

输入: nums = [1,-1,5,-2,3], k = 3
输出: 4 
解释: 子数组 [1, -1, 5, -2] 和等于 3，且长度最长。

method

不仅要和为k，还要长度最长，所以需要用哈希表把前缀和及其下标记录下来

hash[0]=-1，这样如果i=2时cur=6，且k=6，那hash[cur-k]=hash[0]=-1，对应的和为k的区间就是(-1,i]，所以长度为i+1

int maxSubArrayLen(vector<int>& nums, int k) {
    unordered_map<int, int> hash;
    hash[0] = -1;   // 表示前缀和为0的下标为-1
    int res = 0, cur = 0;
    for (int i = 0; i < nums.size(); i++) {
        cur += nums[i]; // 记录前缀和
        if (hash.count(cur) == 0) {
            hash[cur] = i;  // 前面没出现该前缀和才记录
        }
        if (hash.count(cur - k)) {
            int j = hash[cur - k];
            res = max(res, i - j);  // (j,i]的长度
        }
    }
    return res;
}

---

剑指 Offer 57 - II. 和为s的连续正数序列

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。

序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

示例 1：

输入：target = 9
输出：[[2,3,4],[4,5]]

method: 滑动窗口

与『题560』不同的是，这里需要把和为k的子数组输出

维护一个滑动窗口[l,r)的和sum

• sum < target，r++;
• sum > target，l++;
• sum == target，保存结果

vector<vector<int>> findContinuousSequence(int target) {
    int l = 1, r = 1;
    vector<vector<int>> res;
    int sum = 0;
    while (l <= target / 2) {
        if (sum < target) {
            sum += r;
            r++;
        }
        else if (sum > target) {
            sum -= l;
            l++;
        }
        else {
            vector<int> path;
            for (int i = l; i < r; i++) path.push_back(i);
            res.push_back(path);
            sum -= l;
            l++; 
        }
    }
    return res;
}