ผลรวมสองค่าและรูปแบบหลากหลาย

ผลรวมสองค่า: โจทย์สัมภาษณ์คลาสสิก

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]

เหตุใดแฮชแมปจึงใช้แก้โจทย์ผลรวมสองค่าได้

# 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

ผลรวมสองค่าบนอาร์เรย์ที่เรียงลำดับ (ตัวชี้สองตัว)

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]

ผลรวมสามค่า (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]]

ผลรวมสี่ค่า (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]]

ผลรวมสองค่าที่ใกล้เป้าหมายที่สุด

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!

ผลรวมสองค่าที่มีหลายคู่ (ทุกคู่)

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

ผลรวมสองค่าด้วยแฮชแมป: การจัดการค่าซ้ำ

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)...

การสังเกตรูปแบบต่าง ๆ ของผลรวมสองค่า

# 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')

การสื่อสารในการสัมภาษณ์สำหรับโจทย์ผลรวมสองค่า

แบบทดสอบสั้น ๆ

สรุปบทเรียน