6. Two Sum
Najdi v poli nums dvě čísla na různých pozicích, jejichž součet je target. Vrať jejich indexy, menší index první.
Řešení vždy existuje a je jen jedno. Zvládneš to v O(n) pomocí Map?
Příklady
Vstup
nums = [2, 7, 11, 15], target = 9Výstup
[0, 1]Vstup
nums = [3, 2, 4], target = 6Výstup
[1, 2]Ke každému číslu x hledáš doplněk target - x. Ukládej do Map čísla, která už jsou za tebou (hodnota → index), a u každého nového se zeptej, jestli tam jeho doplněk je.
1function twoSum(nums: number[], target: number): number[] {2 const seen = new Map<number, number>(); // hodnota → index3 for (let i = 0; i < nums.length; i++) {4 const need = target - nums[i];5 if (seen.has(need)) return [seen.get(need)!, i];6 seen.set(nums[i], i);7 }8 return [];9}10