투 포인터(Two Pointer) 알고리즘(세 수의 합 구하기)

◇ 알고리즘 정의

- 1차원 배열에서 각 다른 원소를 가르키는 2개의 포인터를 조작해가면서 원하는 값을 탐색하는 알고리즘이다.

◇ 알고리즘 동장방식

◇ 알고리즘 구현

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int[] nums = {0, -5, -2, 4, 6, 9, -1};
        int target = 5;
        int count = 0;

        Arrays.sort(nums);

        for (int i = 0; i < nums.length - 2; i++) {
            int l = i + 1;
            int r = nums.length - 1;

            while (l < r) {
                int sum = nums[i] + nums[l] + nums[r];
                if (sum < target) {
                    l++;
                } else if (sum > target) {
                    r--;
                } else {
                    count++;
                    l++;
                    r--;
                }
            }
        }
        System.out.println(count);
    }
}

◇ 알고리즘 사용처

일반적으로 배열을 순회하며 연산을 할 때 투포인터 알고리즘을 사용하게 되면
(On^i)의 시간복잡도를 (On^(i-1))로 줄일 수 있다.