69 三角形计数（Triangle Count）-北京尧图网络

文章目录1 题目2 解决方案2.1 思路2.2 时间复杂度2.3 空间复杂度3 源码1 题目题目三角形计数Triangle Count描述给定一个整数数组在该数组中寻找三个数分别代表三角形三条边的长度问可以寻找到多少组这样的三个数来组成三角形lintcode题号——382难度——medium样例1输入: [3, 4, 6, 7] 输出: 3 解释: 可以组成的是 (3, 4, 6), (3, 6, 7), (4, 6, 7)样例2输入: [4, 4, 4, 4] 输出: 4 解释:任何三个数都可以构成三角形所以答案为 C(3, 4) 42 解决方案2.1 思路首先三条边在满足abc的前提下只要满足abc即可构成三角形这样我们先对数组进行排序使得按照位置取出来的三个数能够满足abc将c通过循环进行遍历固定再在c位置之前的子数组中找到和的值大于c的两个数即可。2.2 时间复杂度排序的时间复杂度O(n * log n)外层循环的时间复杂度为O(n)在子数组找两数和大于目标值的数的时间复杂度为O(n)总时间复杂度为O(n^2)。2.3 空间复杂度空间复杂度为O(1)。3 源码细节形成三角形的三边条件为(abc abc)即可。先进行排序让有序取出的abc满足abc再固定c去判断abc下标遍历固定c再two sum之前的区间若ab比c大则b不动a右移的所有ab都大于c加入结果之后b左移进行下一轮若ab比c小则需要a左移进行下一轮C版本/** * param S: A list of integers * return: An integer */ int triangleCount(vectorint S) { // write your code here int result 0; if (S.empty()) { return result; } // 先排序确保三个数的大小 abc sort(S.begin(), S.end()); // 固定c的位置 for (int i 2; i S.size(); i) { int target S.at(i); int temp twoSumGreater(S, 0, i - 1, target); // 找到子数组中令两数和大于目标值的结果个数 result temp; } return result; } // left指向aright指向b找到令 abc 的结果 int twoSumGreater(vectorint S, int left, int right, int target) { int result 0; while (left right) { if (S.at(left) S.at(right) target) { left; } else if(S.at(left) S.at(right) target) { result result (right - left); // 直接将left左移的所有结果加入 right--; } } return result; }

69 三角形计数（Triangle Count）

相关推荐

5分钟快速上手：Unity游戏翻译神器XUnity.AutoTranslator完全攻略

网安面试最大骗局：会漏洞复现 ≠ 能上岗，90%新人卡死在这里

ESXi7.0升级8.0后存储vMotion失败 incompatible‑CPU排错完整指南

更多资讯

Claude Code初体验：AI编程Agent实战全记录

毫米波雷达无线感知：从FMCW原始数据到微动特征工程实战

订单CSV导出功能开发实践：从需求评审到代码评审的完整记录

JavaManus：从零实现轻量级Java Agent框架，让大模型无缝接入Spring Boot微服务

Capsolver API接入实战：验证码识别与Selenium自动化集成指南

目标检测入门首选YOLO：环境搭建、数据标注与训练调优完整实战

今日更新

电商智能运营体系从0到1：架构设计、落地步骤与避坑指南

压缩空气储能与热网热惯性联合优化调度：热电联产系统建模与求解

若依框架AI代码生成不稳定？用Agent Skill三层结构+五步法搞定

本周精选

金融AI落地指南：从调研报告到技术选型与工程实践

大模型上下文成本与注意力优化技术深度解析——为何O(n²)平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测

基于GMM的语音识别系统原理与MATLAB实现详解

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？