给定数组，判断是否存在三元组 (a,b,c) 满足 a² + b² = c²。

Write a function returning true if there is a triplet (a, b, c) that satisfies a^2 + b^2 = c^2 given an array of numbers.

题目类型: 技术面试题

这是一道技术面试题，常见于澳洲IT公司面试中。

难度: medium

分类: Algorithms

标签: Pythagorean Triplet, Two Pointers, Two Sum

目标公司: Microsoft

参考答案摘要

答案 暴力三重循环是 O(n^3) 通常不够好。更优做法：先把数组每个元素平方（注意溢出用 long/64-bit），然后排序；固定最大的 c²，从两端指针 i、j 在 [0..c-1] 上做 two-sum：若 arr[i]+arr[j]==c² 返回 true；小了就 i++，大了就 j--。整体复杂度 O(n^2 log n)（含排序），空间 O(1)~O(n)。面试时要强调：排序+双指针把...

本题提供 STAR 原则详细解答和技术解析，登录匠人学院学习中心即可查看完整答案。