🌈個人主頁：秋風(fēng)起，再歸來~
?🔥系列專欄：C++刷題算法總結(jié)? ? ??
🔖克心守己，律己則安

目錄

1、有效三角形的個數(shù)

2、查找總價值為目標(biāo)值的兩個商品

?3、三數(shù)之和

4、四數(shù)之和?

5、完結(jié)散花

---

1、有效三角形的個數(shù)

題目鏈接https://leetcode.cn/problems/valid-triangle-number/description/

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

示例 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

解題思路：

1、 暴力解法：我們可以很輕松的想到枚舉所有的三條變，判斷它們是否可以組成三角形，記錄有效三角形的個數(shù)即可。不過n^3的時間復(fù)雜度會超出時間限制！

class Solution {
public:int triangleNumber(vector<int>& nums) {int len=nums.size(),count=0;for(int a=0;a<len-2;a++){for(int b=a+1;b<len-1;b++){for(int c=b+1;c<len;c++){if(nums[a]+nums[b]>nums[c]&&nums[a]+nums[c]>nums[b]&&nums[b]+nums[c]>nums[a]) count++;}}}return count;}
};

2、更優(yōu)解法：我們先將數(shù)組排序，因?yàn)榕袛嗳齻€數(shù)是否可以構(gòu)成三角形只需要比較較小兩邊之和是否大于第三邊即可。

3、排序后，nums[len-1]的位置就是最大值，我們先用max固定一端，right固定在max左側(cè)，left固定在起點(diǎn)。

4、判斷nums[left]+nums[right]是否大于nums[max]

? ? ? ? a、如果小于，left++

? ? ? ? b、如果大于，count+=（right-left?），固定max和right兩邊后，left是right之后最小的一邊。如果最小的一邊加上right都大于max，那其后的邊一定可以構(gòu)成三角形。所以我們就沒有必要進(jìn)行無意義的枚舉。

? ? ? ? c、此時固定max和right的情況已近枚舉完成，那我們就讓right--。

class Solution {
public:int triangleNumber(vector<int>& nums) {int max=nums.size()-1,count=0;//排序sort(nums.begin(),nums.end());//固定枚舉maxwhile(max>=2){//固定枚舉rightint right=max-1;int left=0;while(left<right){if(nums[left]+nums[right]>nums[max]) {count+=(right-left);right--;}else left++;}max--;}return count;}
};

2、查找總價值為目標(biāo)值的兩個商品

題目鏈接https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/description/

購物車內(nèi)的商品價格按照升序記錄于數(shù)組?price。請在購物車中找到兩個商品的價格總和剛好是?target。若存在多種情況，返回任一結(jié)果即可。

示例 1：

輸入：price = [3, 9, 12, 15], target = 18
輸出：[3,15] 或者 [15,3]

示例 2：

輸入：price = [8, 21, 27, 34, 52, 66], target = 61
輸出：[27,34] 或者 [34,27]

由于題目比較簡單，直接上代碼了！?

class Solution {
public:vector<int> twoSum(vector<int>& price, int target) {int left=0,right=price.size()-1;while(left<right){if(price[left]+price[right]<target) left++;else if(price[left]+price[right]>target) right--;else {//走隱式類型轉(zhuǎn)換return {price[left],price[right]};}}return {-1,-1};}
};

?3、三數(shù)之和

題目鏈接https://leetcode.cn/problems/3sum/description/

給你一個整數(shù)數(shù)組?nums?，判斷是否存在三元組?[nums[i], nums[j], nums[k]]?滿足?i != j、i != k?且?j != k?，同時還滿足?nums[i] + nums[j] + nums[k] == 0?。請你返回所有和為?0?且不重復(fù)的三元組。

注意：答案中不可以包含重復(fù)的三元組。

示例 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 。

解題思路：

1、這個題目的整體思路可以轉(zhuǎn)化為兩數(shù)之和==target，和上一道題目相似，不過在細(xì)節(jié)上還是有些不同。

2、排序后，我們定義target在len-1的位置，left=0，right=target-1。判斷nums[left]+nums[right]==-nums[target]就可以了。

>不過，這里還涉及到去重的問題：

我們找到一個三元組后，left++，right--

a.如果left==left--，那么我們找到的下一個三元組必然和前一個相等！(因?yàn)閘eft和target固定了)

b.同理，如果right==right+1，那么我們找到的下一個三元組必然和前一個相等！

c.再有，如果target==target+1，我們在下一個區(qū)間查找的所有情況再上一個區(qū)間都查找過了！

d.所以這三種情況我們都要跳過相同的元素來進(jìn)行去重操作！

解題代碼：

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> ret;sort(nums.begin(),nums.end());//排序int len=nums.size();for(int target=len-1;target>=2;){if(nums[target]<0) break;//小優(yōu)化int left=0,right=target-1;while(left<right){if(nums[left]+nums[right]<-nums[target]) left++;else if(nums[left]+nums[right]>-nums[target]) right--;else {ret.push_back({nums[left++],nums[right--],nums[target]});//去重while(left<right&&nums[left]==nums[left-1]) left++;while(left<right&&nums[right]==nums[right+1]) right--;}}//去重target--;while(target>=2&&nums[target]==nums[target+1]) target--;}return ret;}
};

4、四數(shù)之和?

題目鏈接https://leetcode.cn/problems/4sum/description/

給你一個由?n?個整數(shù)組成的數(shù)組?nums?，和一個目標(biāo)值?target?。請你找出并返回滿足下述全部條件且不重復(fù)的四元組?[nums[a], nums[b], nums[c], nums[d]]?（若兩個四元組元素一一對應(yīng)，則認(rèn)為兩個四元組重復(fù)）：

• 0 <= a, b, c, d?< n
• a、b、c?和?d?互不相同
• nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按?任意順序?返回答案 。

示例 1：

輸入：nums = [1,0,-1,0,-2,2], target = 0
輸出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2：

輸入：nums = [2,2,2,2,2], target = 8
輸出：[[2,2,2,2]]

解題思路：?

1、這道題目的整體思路和三數(shù)之和差不多，我們可以把上一題理解為兩數(shù)之和==target(0) - 一個數(shù)（自己固定枚舉）。

2、而這道題目無非就是再三數(shù)之和的基礎(chǔ)上，再多枚舉一個數(shù)而已！

解題代碼：

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {int len=nums.size();sort(nums.begin(),nums.end());vector<vector<int>> ret;for(int d=len-1;d>=3;){if(target<0&&nums[0]>=0) break;//小優(yōu)化//三數(shù)之和邏輯for(int c=d-1;c>=2;){long long tmp=(long long)target-nums[c]-nums[d];int left=0;int right=c-1;while(left<right){if(nums[left]+nums[right]<tmp) left++;else if(nums[left]+nums[right]>tmp) right--;else{ret.push_back({nums[left++],nums[right--],nums[c],nums[d]});//left,right去重while(left<right&&nums[left]==nums[left-1]) left++;while(left<right&&nums[right]==nums[right+1]) right--;}}//c去重c--;while(c>=2&&nums[c]==nums[c+1]) c--;}//d去重d--;while(d>=3&&nums[d]==nums[d+1]) d--;}return ret;}
};

5、完結(jié)散花

好了，這期的分享到這里就結(jié)束了~

如果這篇博客對你有幫助的話，可以用你們的小手指點(diǎn)一個免費(fèi)的贊并收藏起來喲~

如果期待博主下期內(nèi)容的話，可以點(diǎn)點(diǎn)關(guān)注，避免找不到我了呢~

我們下期不見不散~~

????