3.44 Two Sum II - Boolean

3.44.1 Problem Metadata

  • Platform: Other
  • Problem ID: N/A
  • Difficulty: Easy
  • URL: N/A
  • Tags:
  • Techniques: Hash Table, Array

3.44.2 Description

Given an integer array nums and an integer k, determine whether there exists a pair of distinct elements whose sum equals k. Return true if such a pair exists; otherwise, return false.

3.44.3 Examples

Example 1

Input: nums = [1,3,7], k = 8
Output: true
Explanation: 1 + 7 = 8.

Example 2

Input: nums = [1,3,7], k = 6
Output: false

3.44.4 Constraints

  • 2 <= nums.length <= 10^5
  • -10^9 <= nums[i], k <= 10^9

3.44.5 Solution - Hash Set

3.44.5.1 Walkthrough

Scan the array once while storing previously seen values in a HashSet. For each num, compute diff = k - num. If diff already exists in the set, we have found a valid pair; otherwise, add num to the set and keep scanning.

3.44.5.2 Analysis

  • Time Complexity: O(n)
  • Space Complexity: O(n) � set of seen values

3.44.5.3 Implementation Steps

  1. Create an empty HashSet<Integer>.
  2. For each num in nums:
    1. Let diff = k - num.
    2. If diff exists in the set, return true.
    3. Otherwise, insert num into the set.
  3. Return false.

3.44.5.4 Code - Java

public boolean sumsToTarget(int[] nums, int k) {
    Set<Integer> seen = new HashSet<>();

    for (int num : nums) {
        int diff = k - num;

        if (seen.contains(diff)) {
            return true;
        }

        seen.add(num);
    }

    return false;
}