투 포인터 기법

사용 시기: O(N) 시간에 배열, 문자열 및 연결 목록과 관련된 문제를 해결하는 최적의 방법입니다.

배열/문자열: 각각 시작과 끝에서 시작하여 둘 다 만날 때까지 두 개의 포인터.
예제 문제:

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        // use two pointer technique because the input is sorted.
        int start = 0; 
        int end = numbers.length - 1;
        int [] result = new int [2];

        while (start < end){
            int sum = numbers[start] + numbers[end];

            if (sum == target){
                result[0] = start + 1;
                result[1] = end + 1;
                break;
            }

            if (sum < target){
                start++;
            } else {
                end--;
            }
        }
        return result;
    }
}


연결된 목록: 하나의 포인터는 느린 속도로 이동하고 다른 포인터는 두 배의 속도로 이동합니다.
예제 문제:

public class Solution {
    public boolean hasCycle(ListNode head) {

        if(head == null){
            return false;
        }

        ListNode slow = head; 
        ListNode fast = head;

        while(fast != null && fast.next != null){

            slow = slow.next;
            fast = fast.next.next;

            if(slow == fast){
                return true;
            }
        }
        return false;
    }
}

좋은 웹페이지 즐겨찾기