[회전 알고리즘] 슬라이딩 창

209.Minimum Size Subarray Sum
전체 배열 과 숫자 s 를 지정 합 니 다. 배열 에서 가장 짧 은 연속 서브 배열 을 찾 아 연속 서브 배열 의 숫자 와 sum > = s 를 찾 아 이 가장 짧 은 연속 서브 배열 의 반환 값 을 되 돌려 줍 니 다.
· 예 를 들 어 주어진 배열 [2, 3, 1, 2, 4, 3], s = 7
· 정 답 은 [4, 3], 귀환 2
폭력 해: 모든 연속 하위 그룹 을 옮 겨 다 니 기 [i, j]
합 sum 을 계산 하고 sum = s 를 검증 합 니 다.
시간 복잡 도 O (n ^ 3)
어떤 방법 으로 시간 복잡 도 를 O (n ^ 2) 로 최적화 할 수 있 습 니까?
 

#include 
#include 
#include 
using namespace std;
class Solution{
public:
    //     :O(n)
    //     :O(1)
    int minSubArrayLen(int s,vector& nums){
        int l = 0;
        int r = -1;  //nums[l...r]     
        int sum = 0;
        int res = nums.size() + 1;
        while(l < nums.size() ){
            if(r + 1 < nums.size() && sum < s){
                r++;
                sum += nums[r];
            }
            else{
                 sum -= nums[l++];
            }
            if(sum >= s){
                res = min(res,r-l+1);
            }
        }
        if(res == nums.size() + 1){
            return 0;
        }
        return res;
    }
    
};
int main(){
    int arr[] = {4,2,4,6,8,9,10};
    vector vec(arr,arr+sizeof(arr)/sizeof(int));
    int ret = Solution().minSubArrayLen(12,vec);
    cout << ret << endl;
    return 0;
}

 
3.Longest Substring  Without Repeating Characters
한 문자열 에서 중복 되 지 않 은 가장 긴 문자열 을 찾 습 니 다.
· "abcabcbb" 와 같이 결 과 는 "abc" 입 니 다.
· "bbbb" 와 같이 결 과 는 "b" 이다.
· "pwkew" 와 같이 결 과 는 "wrk" 입 니 다.
 

#include 
#include 
#include 
#include 
using namespace std;
class Solution{
public:
    int lengthOfLongestSubstring(string s){
        int freq[256] = {0};
        int l = 0;
        int r = -1; //     s[l...r]
        int res;
        while(l < s.size()){
            if(r+1 < s.size() && freq[s[r+1]] == 0){
                r++;
                freq[s[r]]++;
            }
            else{
                freq[s[l++]]--;
            }
            res = max(res, r-l+1);
        }
        return res;
    }
    
};
int main(){
    string arr = "abcabcd";
    int ret = Solution().lengthOfLongestSubstring(arr);
    cout << ret << endl;
    return 0;
}

438.Find All Anagrams in a String
문자열 s 와 비 어 있 는 문자열 p 를 지정 하고 P 의 모든 s 인 anagrams 문자열 의 하위 문자열 을 찾 아 하위 문자열 의 시작 색인 을 되 돌려 줍 니 다.
· 예 를 들 어 s = "cbaeabacd" p = "abc" 돌아 가기 [0, 6]
· 예 를 들 어 s = "abab", p = "ba", 반환 [0, 1, 2]
-- 문자 집합 범 위 는.영문 소문 자
-- 되 돌아 오 는 해 의 순 서 는.임 의
 

#include 
#include 
#include 
#include 
using namespace std;
class Solution{
public:
    vector findAnagramsstring(string nums,string target){
        assert(nums.size() > target.size());
        vector sv(26,0);
        vector pv(26,0);
        vector res;
        for(int i = 0; i < target.size(); i++){
            ++pv[target[i] - 'a'];
            ++sv[nums[i] - 'a'];
        }
        if(sv == pv) res.push_back(0);
        for(int i = target.size(); i < nums.size();i++){
            ++sv[nums[i] - 'a'];
            --sv[nums[i - target.size()] - 'a'];
            if(pv == sv) res.push_back(i - target.size() + 1);
        }
        return res;
    }
    
};
int main(){
    string nums = "cbaebabacdcba";
    string target = "cba";
    vector vec = Solution().findAnagramsstring(nums,target);
    for(int i = 0; i < vec.size(); i++){
        cout << vec[i] << " ";
    }
    cout << endl;
    return 0;
}

 
76.Minimum Window Substring
문자열 S 와 T 를 지정 합 니 다. S 에서 가장 짧 은 하위 문자열 을 찾 습 니 다. T 의 모든 문 자 를 포함 합 니 다.
· 예 를 들 어 S = "ADOBECODEBANC";T = “ABC”
· 결 과 는 'BANC'
-- 문자 범 위 는.
-- 풀 지 않 았 다 면."돌아 가기"
-- 여러 개의 풀이 가 있다 면. 하나만 풀 수 있 을 거 예요.
-- 모든 문 자 를 포함 한 다 는 게 무엇 인가.S=”a”,T = “a”;
 

#include 
#include 
#include 
#include 
using namespace std;
class Solution{
public:
    string MinWinSubstring(string src,string T){
        vector Sv(256,0);
        vector Tv(256,0);
        int lp = -1;
        int rp = -1;
        int answer = 0x7fffffff;
        int begin = 0;
        int lack = T.size();
        for(int i = 0; i < T.size(); i++){
            Tv[T[i]]++;
        }
        
        for(int end = 0; end < src.size(); end++){
            if(Sv[src[end]] < Tv[src[end]]){
                lack--;
            }
            Sv[src[end]]++;
            if(lack == 0){
                while(begin < end && Sv[src[begin]] > Tv[src[begin]]){
                    Sv[src[begin]]--;
                    begin++;
                }
                if(answer > end - begin + 1){
                    answer = end-begin+1;
                    lp = begin;
                    rp = end;
                }
                while(lack == 0){
                    Sv[src[begin]]--;
                    begin += 1;
                    lack += 1;
                }
            }
        }
        return lp == -1 ?" ": src.substr(lp,rp-lp+1);
    }
    
};
int main(){
    string src = "ADOBECODEBANC";
    string T = "ABC";
    string ret = Solution().MinWinSubstring(src,T);
    cout << ret << endl;
    return 0;
}