Kiểm tra 2 số trong mảng có tổng bằng giá trị cho trước C#

Two Sum problem: tìm 2 số trong mảng có tổng = target. Dùng HashSet O(n) hoặc 2 loops O(n²).

Ví dụ minh họa

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        int[] arr = { 7, 4, 6, 2 };
        int target = 8;
        
        Console.WriteLine($"Mảng: [{string.Join(", ", arr)}]");
        Console.WriteLine($"Target: {target}");
        
        // Cách 1: HashSet O(n) - khuyên dùng
        var seen = new HashSet();
        foreach (int x in arr)
        {
            int complement = target - x;
            if (seen.Contains(complement))
            {
                Console.WriteLine($"Tìm thấy: {complement} + {x} = {target}");
            }
            seen.Add(x);
        }
        
        // Cách 2: LINQ (O(n²) do Contains trên array)
        Console.WriteLine("\nLINQ (tìm cặp đầu tiên):");
        var pair = (from i in arr
                    from j in arr
                    where i != j && i + j == target
                    select (i, j)).FirstOrDefault();
        Console.WriteLine($"Cặp: ({pair.i}, {pair.j})");
        
        // Cách 3: Trả về index (LeetCode style)
        var indices = TwoSumIndices(arr, target);
        Console.WriteLine($"\nIndices: [{indices[0]}, {indices[1]}]");
    }
    
    static int[] TwoSumIndices(int[] nums, int target)
    {
        var map = new Dictionary(); // value -> index
        for (int i = 0; i < nums.Length; i++)
        {
            int complement = target - nums[i];
            if (map.TryGetValue(complement, out int j))
                return new[] { j, i };
            map[nums[i]] = i;
        }
        return new int[0];
    }
}

Kết quả đầu ra

Mảng: [7, 4, 6, 2]
Target: 8
Tìm thấy: 2 + 6 = 8
Tìm thấy: 4 + 4 = 8  (nếu cho phép dùng 2 lần cùng index - cần check)

LINQ (tìm cặp đầu tiên):
Cặp: (2, 6)

Indices: [2, 3]

Lưu ý: Code gốc dùng 2 vòng lặp lồng nhau O(n²) và in ra giá trị thay vì index. HashSet O(n) tốt hơn. Cần rõ ràng: có cho phép dùng 2 lần cùng 1 phần tử không (4+4=8).