Find Two Numbers That Add Up to k (Hashing)

Given an array of integers and a target k, return any two numbers from the array (at different positions) whose sum is k. Return Optional.empty() if no such pair exists. Optional is a container that holds either one value or nothing; here it holds an int[] of length 2.

This is the hashing version of Find Two Numbers That Add Up to k. That lesson returns indices, which needs a HashMap. This one returns the values, so a HashSet is enough.

Example 1

Text

Input:  [1, 21, 3, 14, 5, 60, 7, 6], k = 81
Output: (21, 60)

Example 2

Text

Input:  [5, 3, 5], k = 10
Output: (5, 5)    two different 5s

Example 3

Text

Input:  [5, 1], k = 10
Output: empty     one 5 can't be used twice

Brute force: check every pair

Java

import java.util.Arrays;
import java.util.Optional;

public class Main {
    static Optional<int[]> findSum(int[] nums, int k) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if ((long) nums[i] + nums[j] == k) {
                    return Optional.of(new int[]{nums[i], nums[j]});
                }
            }
        }
        return Optional.empty();
    }

    static String show(Optional<int[]> pair) {
        return pair.map(Arrays::toString).orElse("none");
    }

    public static void main(String[] args) {
        System.out.println(show(findSum(new int[]{1, 21, 3, 14, 5, 60, 7, 6}, 81)));
        System.out.println(show(findSum(new int[]{5, 3, 5}, 10)) + " " + show(findSum(new int[]{5, 1}, 10)));
    }
}

Output

[21, 60]
[5, 5] none

Time: O(n²). Space: O(1).

Optimal: a set of values seen so far

For each value x, its partner must be k - x. Walk the array once:

If k - x is already in the set, return (k - x, x).
Otherwise, add x to the set.

Walkthrough with [1, 21, 3, 14, 5, 60, 7, 6], k = 81:

x	partner 81 - x	partner in set?	set after
1	80	no	{1}
21	60	no	{1, 21}
3	78	no	{1, 21, 3}
14	67	no	{1, 21, 3, 14}
5	76	no	{1, 21, 3, 14, 5}
60	21	yes	return (21, 60)

The set holds Long values and the partner is computed as a long, so k - x cannot wrap around for extreme int values.

Java

import java.util.Arrays;
import java.util.HashSet;
import java.util.Optional;
import java.util.Set;

public class Main {
    static Optional<int[]> findSum(int[] nums, int k) {
        Set<Long> seen = new HashSet<>();
        for (int x : nums) {
            long partner = (long) k - x;
            if (seen.contains(partner)) {
                return Optional.of(new int[]{(int) partner, x});
            }
            seen.add((long) x);
        }
        return Optional.empty();
    }

    static String show(Optional<int[]> pair) {
        return pair.map(Arrays::toString).orElse("none");
    }

    public static void main(String[] args) {
        System.out.println(show(findSum(new int[]{1, 21, 3, 14, 5, 60, 7, 6}, 81)));
        System.out.println(show(findSum(new int[]{5, 3, 5}, 10)) + " " + show(findSum(new int[]{5, 1}, 10)));
        System.out.println(show(findSum(new int[]{Integer.MIN_VALUE, 5}, Integer.MAX_VALUE)));
    }
}

Output

[21, 60]
[5, 5] none
none

Time: O(n). Space: O(n).

The order of the two steps matters. Checking for the partner before adding x means x can only pair with an earlier element at a different position. If x were inserted first, [5, 1] with k = 10 would find 5 as its own partner.

Edge cases

No pair: an empty Optional.
Negative numbers and zero: handled, since nothing assumes positive values.
Overflow: k - x in int arithmetic wraps around for extreme values, as Integer.MAX_VALUE - Integer.MIN_VALUE does. The code above widens to long first.