??

611. 有效三角形的個數

611.?有效三角形的個數https://leetcode.cn/problems/valid-triangle-number/

題目描述：

給定一個包含非負整數的數組?nums?，返回其中可以組成三角形三條邊的三元組個數。

解題思路：

本題是一個關于三角形是否能成立的題目，首先我們假設三角形的三邊（a，b,c），我們要保證兩邊之和大于第三邊

?

?題目給我們nums是亂序的，如果我們一個個abc去實驗就是會超時（時間復雜度O^3）

當我們將sort排序一下，這樣的話假設a<b<c的情況下，我們就只要去判斷a+b>c是否成立！

這里我們遍歷每個c（從后往前），這樣時間復雜度就變成了N^2+NlogN也就是N^2

解題代碼：

class Solution {
public:int triangleNumber(vector<int>& nums) {sort(nums.begin(),nums.end());//假設a<b<cint num=0;int n=nums.size();for(int i=n-1;i>=2;i--){int left=0;int right=i-1;while(left<right){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會有三種關系

我們假設sub=right-left

?第一種情況很顯然直接返回就好了我們來研究一下第二種和第三種情況：

解題代碼：

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {int n=nums.size();int left=0;int right=n-1;while(nums[right]>target){right--;}while(left<right){int sub=target-nums[right];if(sub==nums[left]){return {nums[left],nums[right]};}else if(sub>nums[left]){left++;}else//sub<nums[left]{right--;}}return {-1,-1};}
};

?

?