Two Pointer (투포인터)

• 정렬이 되어진 상황에 Two pointer 사용
• 리스트에서 두가지 원소를 가지고 특정한 값을 도출해야할 때 사용
• 아래의 문제는 nums가 주어졌을 때 두 원소를 더해서 target이 되면 True 아니면 False를 return 하는 전형적인 Tow Pointer 문제

import java.util.*;

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] answer = new int[2];
        
        int[][] tmp = new int[nums.length][2];
        int l = 0;
        int r = nums.length - 1;

        for(int i = 0; i < nums.length; i++){
            tmp[i][0] = nums[i];
            tmp[i][1] = i;
        };

        Arrays.sort(tmp, (o1, o2) -> {
            return o1[0]-o2[0];
        });

        while(l < r){
            int sum = tmp[l][0] + tmp[r][0];
            if( sum == target){
                answer[0] = tmp[l][1];
                answer[1] = tmp[r][1];
                break;
            } else if (sum < target){
                l++;
            } else {
                r--;
            };
        };

        Arrays.sort(answer);

        return answer;

        
        
    }
}

• 왼쪽과 오른쪽을 서로 비교하면서 왼쪽이 오른쪽보다 작을 경우 계속 반복문 수행
• list 정렬은 O(nlogn)이고 반복문은 worst로 봤을 때 O(n)임
• ⇒ 여기서 n은 input으로 들어온 nums의 수
• 해당 함수의 시간 복잡도는 가장 worst인 O(nlogn)이 됨

 

출처 : 출처 : https://www.inflearn.com/course/코딩테스트-입문-파이썬/

코딩테스트 [ ALL IN ONE ] - 인프런 | 강의

 

문제 : https://leetcode.com/problems/two-sum/submissions/951433789/