文章目录611.有效三角形的个数一、题目1.题目描述2.题目链接二、题解报告方法一(会超时)思路分析时间复杂度代码实现方法二思路分析时间复杂度代码实现15.三数之和一、题目1.题目描述2.题目链接二、题解报告思路分析时间复杂度代码实现611.有效三角形的个数一、题目1.题目描述给定一个包含非负整数的数组nums返回其中可以组成三角形三条边的三元组个数。示例 1:输入:nums [2,2,3,4]输出: 3解释:有效的组合是:2,3,4 (使用第一个 2)2,3,4 (使用第二个 2)2,2,3示例 2:输入:nums [4,2,3,4]输出: 42.题目链接LeetCode 611.有效三角形的个数二、题解报告方法一(会超时)思路分析使用暴力解法逐个遍历时间复杂度O(N 3 N^3N3)代码实现class Solution{public:inttriangleNumber(vectorintnums){intnnums.size()-1;intcount0;for(inti0;in-1;i)for(intji1;jn;j)for(intkj1;kn;k){if(nums[i]nums[j]nums[k]nums[i]nums[k]nums[j]nums[j]nums[k]nums[i])count;}returncount;}};方法二思路分析确定三条边是否构成三角形其实可以只比一次比如a b c只要满足a b c那么必有a c b和b c a要想实现上面的前提是必须升序因此需要先排序时间复杂度为O(nl o g n log nlogn)然后先固定一个最大数nums[n]再使用指针left指向最小的数right指向次大的数如果nums[left] nums[right] nums[n]说明nums[left]太小了需要left当满足nums[left] nums[right] nums[n]时nums[left]与nums[right]之间的数也都会满足所以count right - left然后再选次大的数依次循环时间复杂度为O(n 2 n^2n2)时间复杂度O(n 2 n^2n2)代码实现class Solution{public:inttriangleNumber(vectorintnums){sort(nums.begin(),nums.end());intcount0;intnnums.size()-1;while(n1){intrightn-1;intleft0;while(leftright){if(nums[left]nums[right]nums[n]){countright-left;right--;}else{left;}}n--;}returncount;}};15.三数之和一、题目1.题目描述给你一个整数数组 nums 判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k 同时还满足 nums[i] nums[j] nums[k] 0 。请你返回所有和为 0 且不重复的三元组。注意答案中不可以包含重复的三元组。示例 1输入nums [-1,0,1,2,-1,-4]输出[[-1,-1,2],[-1,0,1]]解释nums[0] nums[1] nums[2] (-1) 0 1 0 。nums[1] nums[2] nums[4] 0 1 (-1) 0 。nums[0] nums[3] nums[4] (-1) 2 (-1) 0 。不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。注意输出的顺序和三元组的顺序并不重要。示例 2输入nums [0,1,1]输出[]解释唯一可能的三元组和不为 0 。示例 3输入nums [0,0,0]输出[[0,0,0]]解释唯一可能的三元组和为 0 。2.题目链接LeetCode 15.三数之和二、题解报告思路分析题目要求从一组数中找和为0的三个数的所有组合且这些组合不能重复(组合之间三个数不能一摸一样忽略顺序)我们一般会想到暴力解法使用三个for循环但因为要考虑到去重问题所以不好实现这里可以参考以下上面的问题611.有效三角形的个数先排个序在排好序的基础上先固定一个数再去找另外两个数(只要这两个数之和为先前固定的数的相反数,这三个数之和肯定为0但因为是排好序的先固定的数必须为非正数)在找另外两个数的时候因为是排好序的所以可以考虑用双指针如果之和过大right--,如果之和过小left然后要考虑去重问题,因为是排好序的所以重复的数是相邻的每次找到符合的组合之后指针就会移动指向下一个数(包括先固定一个数的指针left,right)这时只需要比较指针之前指向的与现在指向的数是否相同如果相同指针继续移动达到去重的目的时间复杂度排序O(nlog ⁡ n \log nlogn)双指针O(n 2 ) n^2)n2)代码实现class Solution{public:vectorvectorintthreeSum(vectorintnums){vectorvectorintv;sort(nums.begin(),nums.end());intnnums.size();intj0;while(jn-2nums[j]0){intleftj1,rightn-1;inttarget-nums[j];while(leftright){if(nums[left]nums[right]target){right--;}elseif(nums[left]nums[right]target){left;}else{v.push_back({nums[j],nums[left],nums[right]});left,right--;while(nums[right]nums[right1]leftright)right--;while(nums[left]nums[left-1]leftright)left;}}j;while(jn-2nums[j]nums[j-1])j;}returnv;}};