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

目錄

1、有效三角形的個數

2、查找總價值為目標值的兩個商品

?3、三數之和

4、四數之和?

5、完結散花

---

1、有效三角形的個數

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

給定一個包含非負整數的數組?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

解題思路：

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

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)解法：我們先將數組排序，因為判斷三個數是否可以構成三角形只需要比較較小兩邊之和是否大于第三邊即可。

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

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

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

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

? ? ? ? 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、查找總價值為目標值的兩個商品

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

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

示例 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 {//走隱式類型轉換return {price[left],price[right]};}}return {-1,-1};}
};

?3、三數之和

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

給你一個整數數組?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 。

解題思路：

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

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

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

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

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

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

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

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

解題代碼：

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、四數之和?

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

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

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

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

解題代碼：

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)化//三數之和邏輯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、完結散花

好了，這期的分享到這里就結束了~

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

如果期待博主下期內容的話，可以點點關注，避免找不到我了呢~

我們下期不見不散~~

????