LeetCode热题100刷题3：3. 无重复字符的最长子串、438. 找到字符串中所有字母异位词、560. 和为 K 的子数组

3. 无重复字符的最长子串

滑动窗口、双指针

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        //滑动窗口试一下
        //英文字母、数字、符号、空格,ascii 一共包含128个字符
        vector<int> pos(128,-1);
        int ans = 0;
        
        for(int i=0,j=0 ; i<s.size();i++) {
            //s[i]已出现过   pos[s[i]]+1 上次出现位置的下一个位置
            j = max(pos[s[i]]+1,j);
            //比较窗口的大小
            ans = max(ans,i-j+1);
            pos[s[i]] = i;
        }
        return ans;
    }
};

438. 找到字符串中所有字母异位词

统计字符出现的次数

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int ssize = s.size();
        int psize = p.size();
        if(ssize < psize)
            return {};
        vector<int> ans;
        vector<int> count_s(26);
        vector<int> count_p(26);
        for(int i=0;i<psize;i++) {
            count_p[p[i]-'a']++;
            count_s[s[i]-'a']++;
        }
        if(count_s == count_p)
            ans.push_back(0);
        
        for(int i=0;i<ssize-psize;i++) {
            count_s[s[i]-'a']--;
            count_s[s[i+psize]-'a']++;

            if(count_s == count_p) {
                ans.push_back(i+1);
            }
        }
        return ans;
    }
};

560. 和为 K 的子数组

前缀和、哈希表改进的前缀和

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        vector<int> presum(nums.size()+1);
        presum[0] = 0;
        int ans = 0;
        for(int i=0;i<nums.size();i++) {
            presum[i+1] = presum[i] + nums[i];
        }

        for(int i=1;i<=nums.size();i++) {
            for(int j=0;j<i;j++) {
                if(presum[i]-presum[j] == k)
                    ans++;
            }
        }
        return ans;
    }
};

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int n = nums.size();

        unordered_map<int,int> presum;
        presum[0]=1;
        int ans = 0,sum_i = 0;

        for(int i=0;i<n;i++) {
            sum_i += nums[i];

            int sum_j = sum_i-k;
            if(presum.find(sum_j) != presum.end())
                ans += presum[sum_j];
            presum[sum_i]++;
        }
        return ans;
    }
};