Two-Sum ومتغيراته العديدة

Two-Sum: مسألة المقابلات الكلاسيكية

def twoSum(nums, target):
    seen = {}   # val -> index
    for i, x in enumerate(nums):
        complement = target - x
        if complement in seen:
            return [seen[complement], i]
        seen[x] = i
    return []

print(twoSum([2, 7, 11, 15], 9))   # [0, 1]
print(twoSum([3, 2, 4], 6))        # [1, 2]
print(twoSum([3, 3], 6))           # [0, 1]

لماذا تنجح خريطة التجزئة في مسألة Two-Sum؟

# Trace two-sum on [2, 7, 11, 15], target=9
nums, target = [2, 7, 11, 15], 9
seen = {}
for i, x in enumerate(nums):
    complement = target - x
    print(f'i={i} x={x} complement={complement} seen={seen}')
    if complement in seen:
        print(f'  Found: indices [{seen[complement]}, {i}]')
        break
    seen[x] = i

Two-Sum على مصفوفة مرتبة (مؤشران)

def twoSumSorted(numbers, target):
    lo, hi = 0, len(numbers) - 1
    while lo < hi:
        s = numbers[lo] + numbers[hi]
        if s == target:
            return [lo + 1, hi + 1]   # 1-indexed as per LeetCode 167
        elif s < target:
            lo += 1
        else:
            hi -= 1
    return []

print(twoSumSorted([2, 7, 11, 15], 9))   # [1, 2]
print(twoSumSorted([2, 3, 4], 6))         # [1, 3]
print(twoSumSorted([-1, 0], -1))          # [1, 2]

Three-Sum (LeetCode 15)

def threeSum(nums):
    nums.sort()
    result = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i-1]:  # skip duplicates
            continue
        lo, hi = i + 1, len(nums) - 1
        while lo < hi:
            s = nums[i] + nums[lo] + nums[hi]
            if s == 0:
                result.append([nums[i], nums[lo], nums[hi]])
                while lo < hi and nums[lo] == nums[lo+1]: lo += 1
                while lo < hi and nums[hi] == nums[hi-1]: hi -= 1
                lo += 1; hi -= 1
            elif s < 0:
                lo += 1
            else:
                hi -= 1
    return result

print(threeSum([-1, 0, 1, 2, -1, -4]))  # [[-1,-1,2],[-1,0,1]]
print(threeSum([0, 0, 0, 0]))            # [[0,0,0]]

Four-Sum (LeetCode 18)

def fourSum(nums, target):
    nums.sort()
    n, result = len(nums), []
    for i in range(n - 3):
        if i > 0 and nums[i] == nums[i-1]:
            continue
        for j in range(i+1, n-2):
            if j > i+1 and nums[j] == nums[j-1]:
                continue
            lo, hi = j+1, n-1
            while lo < hi:
                s = nums[i]+nums[j]+nums[lo]+nums[hi]
                if s == target:
                    result.append([nums[i],nums[j],nums[lo],nums[hi]])
                    while lo < hi and nums[lo] == nums[lo+1]: lo += 1
                    while lo < hi and nums[hi] == nums[hi-1]: hi -= 1
                    lo += 1; hi -= 1
                elif s < target: lo += 1
                else: hi -= 1
    return result

print(fourSum([1,0,-1,0,-2,2], 0))
# [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Two-Sum الأقرب إلى القيمة المستهدفة

def twoSumClosest(nums, target):
    nums.sort()
    lo, hi  = 0, len(nums) - 1
    best    = float('inf')
    best_pair = None
    while lo < hi:
        s = nums[lo] + nums[hi]
        if abs(s - target) < abs(best - target):
            best = s
            best_pair = (nums[lo], nums[hi])
        if s < target:
            lo += 1
        elif s > target:
            hi -= 1
        else:
            return best_pair  # exact match
    return best_pair

print(twoSumClosest([1, 3, 4, 7, 10], 15))  # (7, 10) => 17, closest to 15
print(twoSumClosest([2, 5, 8, 11], 10))     # (2, 8) => 10, exact!

Two-Sum مع أزواج متعددة (جميع الأزواج)

def twoSumAllPairs(nums, target):
    nums.sort()
    lo, hi = 0, len(nums) - 1
    pairs  = []
    while lo < hi:
        s = nums[lo] + nums[hi]
        if s == target:
            pairs.append((nums[lo], nums[hi]))
            while lo < hi and nums[lo] == nums[lo+1]: lo += 1
            while lo < hi and nums[hi] == nums[hi-1]: hi -= 1
            lo += 1; hi -= 1
        elif s < target:
            lo += 1
        else:
            hi -= 1
    return pairs

print(twoSumAllPairs([1,1,2,3,4,4,5], 5))  # [(1,4),(1,4)-deduped,(2,3)]
# After duplicate-skipping: [(1,4),(2,3)]

عدّ الأزواج التي يقل مجموعها عن K

def countPairsLessThan(nums, k):
    nums.sort()
    lo, hi = 0, len(nums) - 1
    count  = 0
    while lo < hi:
        if nums[lo] + nums[hi] < k:
            count += hi - lo   # all (lo, lo+1)...(lo, hi) are valid
            lo += 1
        else:
            hi -= 1
    return count

print(countPairsLessThan([1, 3, 7, 11, 12], 10))  # (1,3),(1,7),(3,7) => 3
print(countPairsLessThan([3, 5, 2, 3], 7))         # (2,3),(2,3) => 2... verify

Two-Sum باستخدام خريطة تجزئة: معالجة التكرارات

from collections import Counter

def countTwoSumPairs(nums, target):
    freq  = Counter(nums)
    count = 0
    seen  = set()
    for x in freq:
        y = target - x
        if y in freq and (x, y) not in seen:
            if x == y:
                count += freq[x] * (freq[x] - 1) // 2
            else:
                count += freq[x] * freq[y]
            seen.add((x, y))
            seen.add((y, x))
    return count

print(countTwoSumPairs([1,1,2,3,4,4,3], 4))
# Pairs summing to 4: (1,3)x2x2=4, (0+more)...

التعرّف على صيغ نمط Two-Sum

# Summary of approaches by scenario
scenarios = [
    ('Unsorted array, any indices, one pair',   'hash map O(n) time O(n) space'),
    ('Sorted array, any indices, one pair',      'two pointers O(n) time O(1) space'),
    ('All unique pairs summing to target',        'sort + two pointers O(n log n)'),
    ('Three numbers summing to zero (3-sum)',     'sort + fix + two pointers O(n^2)'),
    ('k numbers summing to target (k-sum)',       'sort + k-2 loops + two pointers O(n^(k-1))')
]
for scenario, approach in scenarios:
    print(f'{scenario}\n  => {approach}\n')

التواصل في المقابلة حول Two-Sum

تحقق سريع

ملخص الدرس