15. Two Sum

Origin: Two Sum

Given an array of positive integers and a target integer, return the indices of two elements that sum to the target or [-1, -1] if no such pair exists.

Example 1

Input: taskDurations = [2, 7, 11, 15] slotLength = 9

Output: [0, 1]

Explanation: We look for two durations that sum to the slotLength. Starting with index 0 (2), we need 7 (9-2). At index 1, duration is 7. Thus indices [0, 1] sum to 9.

Example 2

Input: taskDurations = [1, 2, 3, 4] slotLength = 8

Output: [-1, -1]

Explanation: No two durations in the list sum to 8.

Input Format

• An integer n, the number of tasks (0 <= n <= 1000).
• n space-separated positive integers: taskDurations[0], …, taskDurations[n-1] (each between 1 and 1,000,000).
• An integer slotLength, the desired sum (1 <= slotLength <= 2,000,000).

Constraints

• 0 <= n <= 1000
• 1 <= taskDurations[i] <= 1000000
• 1 <= slotLength <= 2000000
• Indices are 0-based
• If a solution exists, return two distinct indices i, j such that 0 <= i < j < n and taskDurations[i] + taskDurations[j] = slotLength
• If no valid pair exists, return [-1, -1]

Output Format

Print two space-separated integers i and j. If multiple valid pairs exist, any one may be printed. If no valid pair exists, print “-1 -1”.

Sample Input 0

0 10

Sample Output 0

-1 -1

Sample Input 1

1 5
5

Sample Output 1

-1 -1

---

函数契约

// 输入：taskDurations（正整数数组），slotLength（目标和）
// 输出：两个索引 [i, j]，满足 taskDurations[i] + taskDurations[j] = slotLength；找不到返回 [-1, -1]
// 边界：空数组 → [-1,-1]；单元素 → [-1,-1]；无解 → [-1,-1]

边界表

场景	返回什么
空数组	[-1, -1]
单元素	[-1, -1]
无解	[-1, -1]
有解	[i, j]
多个解	任意一个

Resolution

我的解法

解法一：暴力枚举

function findTaskPairForSlot(taskDurations: number[], slotLength: number): number[] {
    for (let i = 0; i < taskDurations.length - 1; i++) {
        for (let j = i + 1; j < taskDurations.length; j++) {
            if (taskDurations[i] + taskDurations[j] === slotLength) {
                return [i, j];
            }
        }
    }
    return [-1, -1]
}

双层循环遍历所有对，简单直接。HackerRank 大数据量 Test Case 会超时。

解法二：哈希表（最优解）

function findTaskPairForSlot(taskDurations: number[], slotLength: number): number[] {
    const taskMap = new Map<number, number>();
    for (let i = 0; i < taskDurations.length; i++) {
        const tmp = slotLength - taskDurations[i];
        if (taskMap.has(tmp)) {
            return [taskMap.get(tmp)!, i];
        }
        taskMap.set(taskDurations[i], i);
    }
    return [-1, -1];
}

解题思路

暴力解法枚举所有 (i, j) 对，时间 O(n²)，大数据量超时。

哈希表解法的核心思路：遍历一次，对每个元素算 slotLength - 当前值（补数），查哈希表里有没有这个补数。有就返回索引，没有就把当前值和索引存进哈希表。

用空间换时间：哈希表查找 O(1)，整体 O(n)。和第 9 题双栈法（用另一个栈存历史 min）是同一个思路——拿额外空间换查询效率。

踩坑经历

1. 第一版返回了元素值 [taskDurations[i], taskDurations[j]] 而不是索引 [i, j]，题目要求返回索引。
2. 暴力解法在 LeetCode 上 AC，但 HackerRank 的 Test Case 7 和 8 数据量大，O(n²) 超时，换成哈希表 O(n) 后通过。

复杂度

暴力枚举：

• 时间：O(n²)
• 空间：O(1)

哈希表：

• 时间：O(n)，一次遍历 + O(1) 查找
• 空间：O(n)，哈希表存 n 个元素

参考来源

• 相关文章：算法解题流程：从读题到提交的七步