当前位置：网站首页>leetcode：325. 和等于k的最长子数组长度

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

2022-08-09 22:01:00 【OceanStar的学习笔记】

题目来源

leetcode：325-vip. 和等于k的最长子数组长度

题目描述

在这里插入图片描述

class Solution {
    
public:
    int maxSubArrayLen(vector<int>& nums, int k){
    
      
    }
};

题目解析

思路

先生成一个前缀和数组preSum，其长度为N + 1
那么，如果存在两个索引 $i$ 和 $j$ ，使得 $p re S u m [j] - p re S u m [i] == k$ ，说明找到一个子数组 $[i, j - 1]$ ，子数组和为k
因为要求长度最长，所以定义一个map，其key=preSum[i]，value=i。如果存在同样的preSum[i]，那么保存i较小的哪一个
然后遍历map，找可能的值

class Solution {
    
public:
    int maxSubArrayLen(vector<int>& nums, int k){
    
       int N = nums.size();
       std::vector<int> preSum(N + 1, 0);
       std::map<int, int> map;
       preSum[0] = 0;
       map[0] = 0;
       for (int i = 1; i <= N; ++i) {
    
            preSum[i] = nums[i - 1] + preSum[i - 1];
            if(!map.count(preSum[i])){
    
                map[preSum[i]] = i - 1;
            }

       }
       
       int maxLen = 0;
        for (int i = N; i > maxLen; --i) {
    
            if(map.count(preSum[i] - k)){
    
                maxLen = std::max(maxLen, i - map[preSum[i] - k]);
            }
        }
       return maxLen;
    }
};

简写

我们不需要另外创建一个累积和的数组，而是直接用一个变量sum边累加边处理，而且我们哈希表也完全不用建立和一维数组的映射，只要保存第一个出现该累积和的位置，后面再出现直接跳过，这样算下来就是最长的子数组

class Solution {
    
public:
    int maxSubArrayLen(vector<int>& nums, int k){
    
       int sum = 0, ans = 0;
        unordered_map<int, int> m;
        for (int i = 0; i < nums.size(); ++i) {
    
            sum += nums[i];
            if(sum == k){
    
                ans = i + 1;
            }else if(m.count(sum - k)){
    
                ans = std::max(ans, i - m[sum - k]);
            }
            
            if(!m.count(sum)){
    
                m[sum] = i;
            }
        }
        return ans;
    }
};

测试


int main()
{
    
    Solution solute;
    vector<int> nums{
    1, -1, 5, -2, 3};
    int k=3;
    cout<<solute.maxSubArrayLen(nums,k)<<endl;

    return 0;
}