Need to say the TWO POINTER

Time complextity O(N log n)
보통 정렬된 배열의 pair를 찾는데 쓰임

Rearrange Array Elements by Sign

양수와 음수를 번갈아 정렬

int[] answer = new int[nums.length];

int pos = 0,
    neg = 1;
for(int i=0;i<nums.length;i++){
    if(nums[i] > 0){
        answer[pos] = nums[i];
        pos += 2;
    }
    else{
        answer[neg] = nums[i];
        neg += 2;
    }
}

return answer;

It's quite easy to understand

What is a sliding window

Time complextity O(k*n) (Brute force의 경우 O(n^2))
길거나 짧은 sequence를 특정할 때
주로 array, string에 사용

접근방식

1. fast / slow
   • fast slow 모두 나란히 증가
   • Maximum Number of Vowels in a Substring of Given Length
2. fast / catchup
   • 후순위 탐색이 faster point까지 한 번에 따라잡음
   • Maximum consecutive sum
   • Maximum Average Subarray I
3. fast / 따라가기
   • 선행 탐색 이후 slower 결정
   • Lagging
4. front / back
   • 시작과 끝에서 각자 탐색

Max Consecutive Ones III

0, 1로 구성된 nums array. 0을 k번만큼 뒤집어 1을 연속되게 만든다. 이 때 만들 수 있는 최대 길이

int left = 0, right;
for (right = 0; right < nums.length; right++) {
    if (nums[right] == 0) {
        k--;
    }

    if (k < 0) {
        k += 1 - nums[left];
        left++;
    }
}
return right - left;

0의 숫자를 세지않고 주어진 k를 계속 줄여나간다
while문으로 k를 양수로 돌리지않아도 됨

다른점

• 슬라이딩 윈도우 : 보통 모든 element를 사용하는데 쓰임
• 투포인터 : 보통 2개의 값을 비교하는데 사용

출처

What is Sliding Window Algorithm? Examples?
How to Solve Sliding Window Problems
Is two pointer problem same as sliding window