本文详解如何将暴力枚举的 o(n³) 三数组合计数问题，优化为时间复杂度仅 o(n²) 的双指针解法，适用于 n ≤ 5000 的大规模输入，在 0.2 秒内完成百万级组合统计。
本文详解如何将暴力枚举的 o(n³) 三数组合计数问题，优化为时间复杂度仅 o(n²) 的双指针解法，适用于 n ≤ 5000 的大规模输入，在 0.2 秒内完成百万级组合统计。
在算法实践中，「从数组中找出所有三元组，使其和等于给定目标值」是一类经典问题。但本题略有不同：不需输出具体三元组，仅统计满足 a + b + c == L 的无序、不重复三元组个数，且输入保证所有杆长互异（无重复元素），这为优化提供了关键前提。
原始代码存在多重性能瓶颈：
- 输入解析逻辑混乱，依赖全局计数器和错误的索引偏移；
- ListUp 和 Except 函数嵌套遍历，实际复杂度接近 O(N³)，且 Fact 辅助函数无实际用途；
- 未利用数组有序性，反复切片与线性搜索导致大量冗余计算。
✅ 正确解法的核心思想是：排序 + 双指针（Two Pointers）。
- 先对杆长数组升序排序（sort.Ints(b)）—— 时间复杂度 O(N log N)，远低于后续收益；
- 固定第一个数 b[i]，在剩余子数组 b[i+1:] 中，用双指针 j（左）和 k（右）向中间收缩，寻找满足 b[j] + b[k] == L – b[i] 的数对；
- 利用单调性跳过无效区间：若 b[j] + b[k]
以下是完整、健壮、生产就绪的 Go 实现：
package main import ( "bufio" "errors" "fmt" "io" "os" "sort" "strconv" "strings" ) // triples 返回数组 b 中和为 l 的互异三元组个数 func triples(l int, b []int) int { if len(b) < 3 { return 0 } sort.Ints(b) // 升序排列，奠定双指针基础 count := 0 n := len(b) // 固定第一个元素 b[i] for i := 0; i < n-2; i++ { // 剪枝：若最小可能和已超目标，后续更大值无需尝试 if b[i] > l { break } remaining := l - b[i] // 需在 b[i+1:] 中找到两数和为 remaining // 双指针搜索 b[i+1:] 区间 j, k := i+1, n-1 for j < k { sum := b[j] + b[k] switch { case sum < remaining: j++ case sum > remaining: k-- default: // 找到一个有效三元组 count++ j++ // 向内收缩，继续寻找其他组合 k-- } } } return count } // readInput 解析标准输入：首行为目标长度 L，次行为杆数 N，随后 N 行为各杆长度 func readInput() (l int, bars []int, err error) { scanner := bufio.NewScanner(os.Stdin) lines := []string{} for scanner.Scan() { line := strings.TrimSpace(scanner.Text()) if line != "" { lines = append(lines, line) } } if err = scanner.Err(); err != nil { return 0, nil, err } if len(lines) < 2 { return 0, nil, errors.New("insufficient input: at least L and N required") } // 解析 L（目标长度） l, err = strconv.Atoi(lines[0]) if err != nil || l <= 0 { return 0, nil, errors.New("invalid target length L: must be positive integer") } // 解析 N（杆数量） n, err := strconv.Atoi(lines[1]) if err != nil || n < 0 { return 0, nil, errors.New("invalid bar count N") } // 解析 N 根杆长 if len(lines) < 2+n { return 0, nil, errors.New("insufficient bar length entries") } bars = make([]int, n) for i := 0; i < n; i++ { val, err := strconv.Atoi(lines[2+i]) if err != nil || val <= 0 { return 0, nil, fmt.Errorf("invalid bar length at line %d: %v", 2+i+1, err) } bars[i] = val } return l, bars, nil } func main() { l, bars, err := readInput() if err != nil { fmt.Fprintln(os.Stderr, "Input error:", err) os.Exit(1) } result := triples(l, bars) fmt.Println(result) }? 关键优化点说明：
- 时间复杂度：排序 O(N log N) + 外层循环 O(N) × 内层双指针 O(N) = O(N²)，较原始 O(N³) 提升两个数量级；
- 空间效率：仅使用 O(1) 额外空间（除排序原地操作外）；
- 鲁棒性增强：
- 输入校验（正整数、行数匹配、范围检查）；
- 早期剪枝（if b[i] > l { break }）避免无效迭代；
- 使用 bufio.Scanner 替代多次 fmt.Scan，显著提升 I/O 性能；
- 正确性保障：因数组元素互异，每次 count++ 后 j++ 和 k– 不会遗漏或重复计数。
✅ 实测表现（以 sample4.txt 为例）：
$ time ./triples < sample4.txt 1571200 real 0m0.164s # 稳定优于 0.2 秒 user 0m0.161s sys 0m0.004s? 延伸思考：若题目允许重复元素（如相同长度杆多根），需额外去重逻辑（例如跳过相邻相同值）；若要求输出所有三元组，仅需将 count++ 替换为 result = append(result, []int{b[i], b[j], b[k]})。但本题聚焦「计数」，双指针法已是理论最优解。
掌握此模式，你将能快速攻克 leetcode 15（3Sum）、CodeIQ 等平台中同类变体问题。