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]
输出: 4

2.题目链接

LeetCode 611.有效三角形的个数

二、题解报告

方法一(会超时)：

思路分析

使用暴力解法，逐个遍历

时间复杂度

O(N 3 N^3N3)

代码实现

class Solution{public:inttriangleNumber(vector<int>&nums){intn=nums.size()-1;intcount=0;for(inti=0;i<n-1;i++)for(intj=i+1;j<n;j++)for(intk=j+1;k<=n;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(vector<int>&nums){sort(nums.begin(),nums.end());intcount=0;intn=nums.size()-1;while(n>1){intright=n-1;intleft=0;while(left<right){if(nums[left]+nums[right]>nums[n]){count+=right-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:vector<vector<int>>threeSum(vector<int>&nums){vector<vector<int>>v;sort(nums.begin(),nums.end());intn=nums.size();intj=0;while(j<n-2&&nums[j]<=0){intleft=j+1,right=n-1;inttarget=-nums[j];while(left<right){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[right+1]&&left<right)right--;while(nums[left]==nums[left-1]&&left<right)left++;}}j++;while(j<n-2&&nums[j]==nums[j-1])j++;}returnv;}};