'슬라이딩 창'과 관련 된 알고리즘 면접 문 제 를 몇 가지 공유 합 니 다.

프롤로그 과학 보급:미끄럼 창 알고리즘 이 무엇 입 니까?
미끄럼 문 제 는 미끄럼 창 을 포함 합 니 다.큰 배열 에서 실행 되 는 하위 목록 입 니 다.이 배열 은 기본 요소 집합 입 니 다.
배열[a b c d e f g h]이 있다 고 가정 하면 크기 가 3 인 미끄럼 창 이 그 위 에서 미 끄 러 지면 다음 과 같 습 니 다.

[a b c]
 [b c d]
 [c d e]
  [d e f]
  [e f g]
   [f g h]

일반적인 상황 에서 이 창 을 사용 하여 배열 의 합 법 적 인 구간 에서 미 끄 러 지 는 동시에 유용 한 데 이 터 를 동적 으로 기록 하 는 경우 가 많 습 니 다.많은 경우 알고리즘 의 효율 을 크게 향상 시 킬 수 있 습 니 다.
1.슬라이딩 창 최대 치
제목 은 LeetCode 에서 239 번 문제:미끄럼 창 최대 값 입 니 다.제목 난이 도 는 하 드 로 현재 통 과 률 은 40.5%다.
제목 설명
배열 nums 를 지정 합 니 다.k 크기 의 미끄럼 창 이 배열 의 맨 왼쪽 에서 배열 의 맨 오른쪽 으로 이동 합 니 다.미끄럼 창 k 에 있 는 숫자 만 볼 수 있 습 니 다.슬라이딩 창 은 매번 오른쪽으로 한 분만 이동 합 니 다.
슬라이딩 창의 최대 값 을 되 돌려 줍 니 다.
예시:
입력:nums=[1,3,-1,-3,5,3,6,7],그리고 k=3
출력:[3,3,5,5,6,7]
설명:
  슬라이딩 창의 위치                최대 치
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7
제목 해석
하나의 쌍 단 대기 열 을 이용 하여 대기 열 에 요 소 를 배열 에 저장 하고 대기 열의 엄격 한 체감 을 유지 합 니 다.즉,유지 팀 의 첫 번 째 요 소 는 가장 크다 고 합 니 다.새로운 요 소 를 옮 겨 다 닐 때 대기 열 에 현재 요소 보다 작은 것 이 있 으 면 대기 열 을 제거 하여 대기 열의 체감 을 확보 합 니 다.대기 열 요소 의 위치 차이 가 k 보다 크 면 팀 의 첫 번 째 요 소 를 제거 합 니 다.
추가:양 끝 대기 열 이란 무엇 인가(Dqueue)
Deque 의 의 미 는'double ended queue',즉 쌍 단 대기 열 입 니 다.대기 열과 창고 의 성질 을 가 진 데이터 구조 입 니 다.말 그대로 전단 과 백 엔 드 가 삽입 과 삭 제 를 지원 하 는 대기 열 입 니 다.
Deque 는 Queue(대기 열)에서 계승 되 며,Array Deque,LinkedList 등 이 직접 실 현 됩 니 다.
애니메이션 설명

코드 구현

class Solution {
 public int[] maxSlidingWindow(int[] nums, int k) {
  //   ，           ，  k > 0。      ，         nums = [], k = 0，          
  if (nums == null || nums.length < k || k == 0) return new int[0];
  int[] res = new int[nums.length - k + 1];
  //    
  Deque<Integer> deque = new LinkedList<>();
  for (int i = 0; i < nums.length; i++) {
   //       ，            
   while (!deque.isEmpty() && nums[deque.getLast()] < nums[i]) {
    deque.removeLast();
   }
   deque.addLast(i);
   //       
   if (deque.getFirst() == i - k) {
    deque.removeFirst();
   }
   //    
   if (i >= k - 1) {
    res[i - k + 1] = nums[deque.getFirst()];
   }
  }
  return res;
  }
}

2.중복 문자 없 는 최 장 하위 문자열
제목 은 LeetCode 의 세 번 째 문제 에서 유래 합 니 다.중복 문자 가 없 는 가장 긴 문자열 입 니 다.제목 난이 도 는 미 디 엄 으로 현재 통과 율 은 29.0%다.
제목 설명
문자열 을 지정 합 니 다.중복 문자 가 없 는 가장 긴 문자열 의 길 이 를 찾 아 보 세 요.
예시 1:
입력:"abcabcbb"
출력:3
해석:중복 문자 가 없 는 가장 긴 문자열 은"abc"이기 때문에 길 이 는 3 입 니 다.
제목 해석
256 비트 크기 의 전체 배열 free g 를 만 들 고 문자 와 나타 나 는 위치 사이 의 맵 을 만 듭 니 다.
미끄럼 창 을 유지 합 니 다.창 안에 있 는 문 자 는 중복 되 지 않 습 니 다.가능 한 한 창의 크기 를 늘 리 고 창 은 계속 오른쪽으로 미 끄 러 집 니 다.
(1)현재 옮 겨 다 니 는 문자 가 나타 나 지 않 으 면 오른쪽 경 계 를 직접 확대 합 니 다.
(2)현재 옮 겨 다 니 는 문자 가 나타 나 면 창 을 축소 하고(왼쪽 색인 을 오른쪽으로 이동)현재 옮 겨 다 니 는 문 자 를 계속 관찰 합 니 다.
(3)왼쪽 색인 이 더 이상 이동 할 수 없 을 때 까지 반복(1)(2);
(4)결과 res 를 유지 합 니 다.매번 나타 난 창 크기 로 결과 res 를 업데이트 하고 마지막 으로 res 로 결 과 를 가 져 옵 니 다.
애니메이션 설명

코드 구현

//     
//      : O(len(s))
//      : O(len(charset))
class Solution {
public:
 int lengthOfLongestSubstring(string s) {
  int freq[256] = {0};
  int l = 0, r = -1; //     s[l...r]
  int res = 0;
  //       l == 0; r == -1        
  //  l == s.size(); r == s.size()-1        
  //             ,   freq,                     
  while(l < s.size()){
   if(r + 1 < s.size() && freq[s[r+1]] == 0){
    r++;
    freq[s[r]]++;
   }else { //r     || freq[s[r+1]] == 1
    freq[s[l]]--;
    l++;
   }
   res = max(res, r-l+1);
  }
  return res;
 }
};

3.중복 원소 존재 II
제목 은 LeetCode 에서 219 번 문제:중복 요소 II 가 존재 합 니 다.제목 난이 도 는 Easy 로 현재 통과 율 은 33.9%다.
제목 설명
하나의 정수 배열 과 하나의 정수 k 를 지정 하여 배열 에 두 개의 서로 다른 색인 i 와 j 가 존재 하 는 지 판단 하여 nums[i]=nums[j]를 만 들 고 i 와 j 의 차 이 는 절대 값 이 k 로 가장 크다.
예시 1:
입력:nums=[1,2,3,1],k=3
출력:true
예시 2:
입력:nums=[1,0,1],k=1
출력:true
예시 3:
입력:nums=[1,2,3,1,2,3],k=2
출력:false
제목 해석
미끄럼 창 과 탐색 표 로 해결 합 니 다.

검색 표 record 를 설정 하여 매번 에 삽 입 된 요 소 를 저장 합 니 다.record 의 최대 길 이 는 k

입 니 다.

배열 nums 를 옮 겨 다 니 며 옮 겨 다 닐 때마다 record 에서 같은 요소 가 있 는 지 찾 습 니 다.존재 하면 true 로 돌아 가 옮 겨 다 니 며 끝 납 니 다

이번에 record 에서 찾 지 못 하면 이 요 소 를 record 에 삽입 한 다음 record 의 길이 가 k+1

인지 확인 합 니 다.

이때 record 의 길이 가 k+1 인지 여 부 는 record 의 요 소 를 삭제 합 니 다.이 요소 의 값 은 nums[i-k]

입 니 다.

전체 배열 nums 를 옮 겨 다 니 며 찾 지 못 하면 false 로 돌아 갑 니 다.

코드 구현

//      : O(n)
//      : O(k)
class Solution {
public:
 bool containsNearbyDuplicate(vector<int>& nums, int k) {
  if(nums.size() <= 1) return false;
  if(k <= 0) return false;
  unordered_set<int> record;
  for(int i = 0 ; i < nums.size() ; i ++){
   if(record.find(nums[i]) != record.end()){
    return true;
   }
   record.insert(nums[i]);
   //   record    k   
   //                  ,      k+1   
   if(record.size() == k + 1){
    record.erase(nums[i - k]);
   }
  }
  return false;
 }
};

4.길이 가 가장 작은 하위 그룹
제목 은 LeetCode 에서 209 번 문제:길이 가 가장 작은 하위 배열 에서 유래 했다.제목 난이 도 는 미 디 엄 으로 현재 통과 율 은 37.7%다.
제목 설명
n 개의 정수 가 함 유 된 배열 과 하나의 정수 s 를 지정 하여 이 배열 에서 그 와≥s 의 길 이 를 만족 시 키 는 가장 작은 연속 서브 배열 을 찾 아 라.조건 에 맞 는 연속 서브 그룹 이 존재 하지 않 으 면 0 으로 돌아 갑 니 다.
예시:
입력:s=7,nums=[2,3,1,2,4,3]
출력:2
해석:하위 배열[4,3]은 이 조건 에서 길이 가 가장 작은 연속 하위 배열 이다.
제목 해석
두 개의 포인터 left 와 right 를 정의 하여 하위 배열 의 좌우 경계 위 치 를 기록 합 니 다.
(1)하위 배열 과 주어진 값 보다 크 거나 right 가 배열 의 끝 에 도달 할 때 까지 right 를 오른쪽으로 이동 합 니 다.
(2)최 단 거 리 를 업데이트 하고 left 를 오른쪽으로 이동 시 키 며 sum 에서 이동 하 는 값 을 뺀 다.
(3)오른쪽 이 끝 날 때 까지(1)(2)절 차 를 반복 하고 왼쪽 이 임계 위치 에 도착 합 니 다.
애니메이션 설명
미끄럼 창의 길 이 를 0 으로 설정 하고 축 의 맨 왼쪽 에 있 습 니 다.
1.슬라이딩 창 오른쪽 R 은 구간 이 주어진 조건,즉 7 이상 을 만족 시 킬 때 까지 이동 합 니 다.이때 세 번 째 요소 2 에서 멈 추고 현재 의 최 적 길 이 는 4 입 니 다.
그림 1

2.슬라이딩 창 왼쪽 L 이 이동 을 시작 하여 슬라이딩 창의 크기 를 줄 이 고 첫 번 째 요소 3 에서 멈 춥 니 다.이때 구간 과 6 이 므 로 구간 과 주어진 조건 을 만족 시 키 지 않 습 니 다(이때 7 이상 이 아 님)
그림 2

3.슬라이딩 창 오른쪽 R 을 계속 이동 하고 네 번 째 요소 4 에서 멈 춥 니 다.이때 와 비트 10 이지 만 가장 좋 은 길 이 는 4 입 니 다.
그림 3

코드 구현

//        
//      : O(n)
//      : O(1)
class Solution {
 public int minSubArrayLen(int s, int[] nums) {
  int l= 0,r = -1; // nums[l...r]        
  int sum = 0;
  int result = nums.length + 1;
  while (l < nums.length){ //             ,     

   if( r+1 <nums.length && sum < s){
    r++;
    sum += nums[r];
   }else { // r        sum >= s
    sum -= nums[l];
    l++;
   }

   if(sum >= s){
    result = (r-l+1) < result ? (r-l+1) : result ;
   }
  }
  if(result==nums.length+1){
   return 0;
  }
  return result;
 }
}

총결산
위 에서 말 한 것 은 소 편 이 여러분 에 게 소개 한'미끄럼 창'과 관련 된 알고리즘 면접 문 제 를 몇 가지 공유 하 는 것 입 니 다.여러분 에 게 도움 이 되 기 를 바 랍 니 다.궁금 한 점 이 있 으 면 메 시 지 를 남 겨 주세요.소 편 은 제때에 답 해 드 리 겠 습 니 다.여기 서도 저희 사이트 에 대한 여러분 의 지지 에 감 사 드 립 니 다!
만약 당신 이 본문 이 당신 에 게 도움 이 된다 고 생각한다 면,전 재 를 환영 합 니 다.번 거 로 우 시 겠 지만 출처 를 밝 혀 주 십시오.감사합니다!