BOJ. Sum of Two Numbers (3273)

The input contains N distinct positive integers and a target X (1 ≤ N ≤ 100,000, each value is at most 1,000,000). Count unordered pairs of different input elements whose sum is X.

Sort the values, then keep two pointers at the smallest and largest remaining values. If their sum is too small, the left value cannot form a target pair with any remaining value, so move the left pointer right. If the sum is too large, the right value cannot pair with any remaining value, so move the right pointer left. On a match, count the pair and move both pointers: this consumes each endpoint, so the same pair cannot be counted again. The pointers meet after every candidate has been considered; if none matched, the count remains zero. This also works for the smallest valid input (N = 1), since the pointers start equal and no pair is counted.

The sum is computed as long to avoid overflow. Sorting takes O(N log N) time; the pointer scan takes O(N), for O(N log N) overall and O(N) space for the input array.

Java

import java.io.BufferedInputStream;
import java.io.IOException;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        FastScanner input = new FastScanner();
        int n = input.nextInt();
        int[] values = new int[n];
        for (int i = 0; i < n; i++) {
            values[i] = input.nextInt();
        }
        int target = input.nextInt();

        Arrays.sort(values);
        int left = 0;
        int right = n - 1;
        int count = 0;
        while (left < right) {
            long sum = (long) values[left] + values[right];
            if (sum == target) {
                count++;
                left++;
                right--;
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }

        System.out.println(count);
    }

    private static class FastScanner {
        private final BufferedInputStream input = new BufferedInputStream(System.in);

        int nextInt() throws IOException {
            int c;
            do {
                c = input.read();
            } while (c <= ' ' && c != -1);

            int value = 0;
            while (c > ' ') {
                value = value * 10 + c - '0';
                c = input.read();
            }
            return value;
        }
    }
}