一个数组中满足一定约束连续数字个数

刺骨的言语ヽ痛彻心扉 2022-03-22 10:18 162阅读 0赞

这是一个类型题，在leetcode中很常见。这里只是阐述下思想。  
暴力解法一般是O(N2)，如果观察其他大佬的代码，发现都使用了个异曲同工的解法。  
使用一个累积运算的变量s，这个变量累积的运算有具体题来决定。  
先创建一个map，一般来说选择unorder\_map,这样查找某个元素的复杂度是0(1)，（因为这个算法大部分时间是查询操作）  
那么遍历一遍数组，每一次循环要做的事情：

对s进行一次运算
    使用运算结果在map中查找对应元素，并+给结果变量
    将map中相应元素++

算法思想：  
对于某种运算（如加法）  
当s的值再次出现时，说明这之间的所有值(包括末项，不包括首项)的和为0。  
也可以说  
当s的值出现时，说明从s==n的元素到当前的元素，中间数字(包括末项，不包括首项)的和为s-n。  
对其他运算也可以使用相似的思想。

最后，给一个例子：  
***leetcode 566题***

***给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。***

#include <iostream>
    #include <vector>
    #include <unordered_map>
    using namespace std;
    
    int subarraySum(vector<int> &nums, int k)
    { 
        int subarraySum(vector<int>& nums, int k) { 
            unordered_map<int ,int>m;
            m[0]=1;
            int count=nums.size();
            int sum=0;
            int ans=0;
            for(int i=0;i<count;i++)
            { 
                sum+=nums[i];
                ans+=m[sum-k];
                m[sum]++;
            }
            return ans;    
        }
    
    int main()
    { 
        vector<int> a{ 1, -1, 1, -1, 1, -1, 1, -1, 1, -1};
        subarraySum(a, 3);
        return 0;
    }