网站建设公司 南宁,wordpress dnax,dns网站建设,网络推广工资611. 有效三角形的个数 611. 有效三角形的个数https://leetcode.cn/problems/valid-triangle-number/
题目描述#xff1a;
给定一个包含非负整数的数组 nums #xff0c;返回其中可以组成三角形三条边的三元组个数。 解题思路#xff1a; 本题是一个关于三角形是否能成立…
611. 有效三角形的个数 611. 有效三角形的个数https://leetcode.cn/problems/valid-triangle-number/
题目描述
给定一个包含非负整数的数组 nums 返回其中可以组成三角形三条边的三元组个数。 解题思路 本题是一个关于三角形是否能成立的题目首先我们假设三角形的三边ab,c我们要保证两边之和大于第三边 题目给我们nums是乱序的如果我们一个个abc去实验就是会超时时间复杂度O^3 当我们将sort排序一下这样的话假设abc的情况下我们就只要去判断abc是否成立 这里我们遍历每个c从后往前这样时间复杂度就变成了N^2NlogN也就是N^2 解题代码
class Solution {
public:int triangleNumber(vectorint nums) {sort(nums.begin(),nums.end());//假设abcint num0;int nnums.size();for(int in-1;i2;i--){int left0;int righti-1;while(leftright){if(nums[left]nums[right]nums[i]){num(right-left);right--;}else{left;}}}return num;}
}; 剑指 Offer 57. 和为s的两个数字
剑指 Offer 57. 和为s的两个数字https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/
题目描述
输入一个递增排序的数组和一个数字s在数组中查找两个数使得它们的和正好是s。如果有多对数字的和等于s则输出任意一对即可。 解题思路 首先本题是升序数组这里如果我们用暴力的话会超时 这里我们使用双指针我们让一个指向头left一个指向尾right这里left、right和target会有三种关系 我们假设subright-left 第一种情况很显然直接返回就好了我们来研究一下第二种和第三种情况 解题代码
class Solution {
public:vectorint twoSum(vectorint nums, int target) {int nnums.size();int left0;int rightn-1;while(nums[right]target){right--;}while(leftright){int subtarget-nums[right];if(subnums[left]){return {nums[left],nums[right]};}else if(subnums[left]){left;}else//subnums[left]{right--;}}return {-1,-1};}
};
