배열에서 합이 n인 연속된 구간 찾기 : 투포인터(Two Pointers)

* 2022년 10월 19일 velog에 작성했던 게시글을 옮겨온 글입니다.

 

원소들의 합이 n이 되는 연속된 구간을 찾는 유형의 문제를 종종 볼 수 있는데 투 포인터 알고리즘을 통하여 해결 할 수 있다.

 

📈 시간 복잡도

선형 탐색 O(N)

 

1. 시작점과 끝점을 0번째 인덱스로 지정한다.
2. 부분합이 5와 같을 경우 카운트 한다.
3. 부분합이 5보다 작기 때문에 끝점을 1 증가시킨다.
4. 반대일 경우 시작점을 1 증가시킨다.
5. 2~4를 반복한다.

 

 

 

부분합이 1이므로 끝점을 1증가 시킨다.

 

 

 

부분합이 3이므로 마찬가지로 끝점을 1증가 시킨다.

 

 

부분합이 6이므로 시작점을 1증가 시킨다.

 

 

부분합이 5이므로 카운트를 한다. 이후 끝점을 1증가 시킨다. 반복한다.

 

문제

 

[LeetCode] 977. Squares of a Sorted Array

Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

 

예시

 

Example 1:

Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Explanation: After squaring, the array becomes [16,1,0,9,100].
After sorting, it becomes [0,1,9,16,100].

Example 2:

Input: nums = [-7,-3,2,3,11]
Output: [4,9,9,49,121]

 

제한 조건

 

Constraints:

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums is sorted in non-decreasing order.
  
  

나의 풀이

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortedSquares = function(nums) {
    let l = 0;
    let r = nums.length - 1;
    let pointer = r;
    const result = new Array(r);

    while (l <= r) {
        const left = Math.abs(nums[l]);
        const right = Math.abs(nums[r]);

        if(left > right) {
            result[pointer] = left ** 2;
            l++;
            pointer--;
        } else {
            result[pointer] = right ** 2;
            r--;
            pointer--;
        }
    }
    return result;
};

1. 이미 정렬된 배열이기 때문에 양끝을 기준으로 오른쪽점을 포인터로 지정한다.
2. 두 요소의 절대값을 비교후 왼쪽점의 요소가 크다면 결과 배열의 포인터 인덱스에 왼쪽점 요소의 제곱을 할당한다. 그 후 왼쪽점을 1 증가시키고 포인터를 1감소시킨다.
3. 반대로 오른쪽 요소가 크다면 오른쪽점 요소의 제곱을 결과 배열의 포인터 인덱스에 할당한다. 그 후 오른쪽점을 1감소시키고 포인터를 1감소시킨다.
4. l <= r 일동안 반복한 후 결과 배열을 리턴한다.