32. Zero-Sum Triplets within Sliding Window

Origin: Zero-Sum Triplets within Sliding Window

Given an integer array and an integer windowSize, find all unique triplets at indices i < j < k such that array[i] + array[j] + array[k] = 0 and k - i + 1 <= windowSize. Return the triplets without duplicates.

三个元素之和为零，且三个索引的距离在窗口范围内。

Example

Input: readings = [1, -2, 1, 0, 5], windowSize = 3

Output: [[1, -2, 1]]

Explanation: 窗口大小 3，所有长度 <= 3 的子数组里找三数之和为 0。

• (0,1,2): 1+(-2)+1=0 ✓
• (1,2,3): -2+1+0=-1
• (2,3,4): 1+0+5=6

只有 [1, -2, 1] 满足。

Input Format

• 第一行：n（数组长度）
• 第二行：n 个整数
• 第三行：windowSize

Constraints

• 1 <= readings.length <= 100000
• -100000 <= readings[i] <= 100000
• 1 <= windowSize <= readings.length

Output Format

返回二维数组，每个元素是 [x, y, z] 且 x+y+z=0、索引距离 <= windowSize。三元组唯一，顺序任意。

Sample Input 0

1
1
1

Sample Output 0

[]

Sample Input 1

2
1 -1
2

Sample Output 1

[[-1, 1, 0]] 或 [[1, -1, 0]]

注意：Sample Input 1 的数组只有 2 个元素，无法组成三元组。具体输出以 HackerRank 为准。

---

函数契约

// 输入：readings（整数数组），windowSize（窗口大小）
// 输出：所有满足条件的唯一三元组 [x, y, z]
// 约束：i < j < k，k - i + 1 <= windowSize，x + y + z = 0
// 边界：数组长度 < 3 → []；windowSize < 3 → []；无解 → []

边界表

场景	返回什么
数组长度 < 3	[]
windowSize < 3	[]
无满足条件的三元组	[]
正常场景	所有唯一三元组

Resolution

⚠️ 本题测试用例有问题，评论区几乎所有用户都只能通过 9/16，跳过。

我的解法（滑动窗口 + 暴力枚举）

function findZeroSumTripletsInWindow(readings: number[], windowSize: number): number[][] {
    if (windowSize < 3 || readings.length < 3) return []
    let start = 0;
    let end = start + windowSize - 1
    const resultSet: Set<string> = new Set()
    while (end < readings.length) {
        for (let i = start; i <= end; i++) {
            for (let j = i + 1; j <= end; j++) {
                for (let k = j + 1; k <= end; k++) {
                    if (readings[i] + readings[j] + readings[k] === 0) {
                        resultSet.add([readings[i], readings[j], readings[k]].sort((a, b) => a - b).join(','))
                    }
                }
            }
        }
        end++
        start++
    }
    return Array.from(resultSet).map((res) => res.split(',').map((s) => Number(s)))
}

解题思路

滑动窗口内暴力枚举三元组，用 Set + sort + join 去重。

复杂度

• 时间：O(n × w³)，w 是窗口大小
• 空间：O(结果数量)

参考来源

• 相关文章：算法解题流程：从读题到提交的七步
• 相关题型：滑动窗口（如果有）
• 相关题目：15. Two Sum — 两数之和的升级版，三数之和