[Two Pointers, Medium] Max Number of K-Sum Pairs

https://leetcode.com/problems/max-number-of-k-sum-pairs/description/?envType=study-plan-v2&envId=leetcode-75

O(N^2)로 푸는 방법은 배제한다.

투포인터로 푸는 방법은 left + right가 k와 같은지 보면 되고 이 때 answer++, left++, right-- 하는 것은 당연한데

문제는 언제 left 또는 right 포인터를 이동시켜야 하는가이다.
이 문제는 딱히 정렬에 대한 문제가 없으므로 nums배열 자체를 정렬시킨다면 어느 쪽으로 탐색할지가 명확해진다.

합이 k보다 크면 right--, 그렇지 않다면 left++다. (정렬되어 있으니까)

다만.. DualPivotQuicksort 특성상 평균 : O(nlog(n)) / 최악 : O(n^2)이다.

class Solution {
    public int maxOperations(int[] nums, int k) {
        Arrays.sort(nums);

        int answer = 0;

        int left = 0;
        int right = nums.length - 1;

        while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum == k) {
                answer++;
                left++;
                right--;
            } else if (sum > k) {
                right--;
            } else {
                left++;
            }
        }

        return answer;
    }
}

솔루션 참고해보면 보수를 이용한 HashMap 방법이 O(N)으로 더 빠르다는데
실제로는 그렇지 않다.

해시 충돌에 의한 체이닝 오버헤드 또는 리사이징 오버헤드?
아니면 map 사용에 따른 GC 오버헤드?

그리고 Random Access VS Sequential Access 차이 등이 있을 것 같다.

실제 런타임은 다양한 변수가 존재한다는 것을 이해했다.