Two Sum Exists
Medium · rating 1250 · Arrays, Hashing
The first line contains n and a target t. The second line contains n integers. Print YES if some two of them sum to t, otherwise NO.
Constraints: 1 ≤ n ≤ 105
Editorial
Two Sum Exists is the yes/no variant of Two Sum: does some pair of numbers add up to the target? Keep seen values in a hash set; for each x, if target − x was already seen, a pair exists.
seen = set()
found = False
for x in nums:
if target - x in seen:
found = True; break
seen.add(x)
print('YES' if found else 'NO')Complexity
Time: O(n). Space: O(n). (The classic Two Sum returns the pair's indices; here only existence is needed.)
Related problems
- Most Common Value — Medium
- Most Frequent Element — Medium
- Count Pairs With Sum — Medium
- Count Pairs With Difference — Medium
- Count Pairs with Sum — Medium
- Find the Duplicate — Medium