---

前言

---

一、有效三角形的個數

1.1 題目描述

描述：

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

---

提示:

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 1000

---

示例1：

---

示例2：

---

1.2 題目解析

1.2.1 算法原理

---

1.2.2 代碼編寫

---

1.2.3 題目總結

---

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

描述：

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

---

提示：

• 1 <= price.length <= 10^5
• 1 <= price[i] <= 10^6
• 1 <= target <= 2*10^6

---

示例1：

---

示例2：

---

2.2 題目解析

2.2.1 算法原理

解法（雙指針 + 對撞指針）：

算法思路：

注意到本題是升序的數組，因此可以用「對撞指針」優化時間復雜度。

---

算法流程（附帶算法分析，為什么可以使用對撞指針）：

步驟a.

初始化 left ， right 分別指向數組的左右兩端

（這里不是我們理解的指針，而是數組的下 標）

---

步驟b.

當 left < right 的時候，一直循環。

情況i. 當 nums[left] + nums[right] == target 時，說明找到結果，記錄結果，并且 返回；

情況ii. 當 nums[left] + nums[right] < target 時：

（1）對于 nums[left] 而言，此時 nums[right] 相當于是 nums[left] 能碰到的 最大值。

（別忘了，這里是升序數組哈）。

如果此時不符合要求，說明在這個數組里面， 沒有別的數符合 nums[left] 的要求了

（最大的數都滿足不了你，你已經沒救了）。

因此，我們可以大膽舍去這個left下標的數，讓 left++ ，去比較下一組數據；

（2）那對于 nums[right] 而言，由于此時兩數之和是小于目標值的，?nums[right] 還可以選擇比 nums[left] 大的值繼續努力達到目標值，因此 right 指針我們按 兵不動；

情況iii.

當 nums[left] + nums[right] > target 時，

同理我們可以舍去 nums[right] （最小的數都滿足不了你，你也沒救了）。

讓 right-- ，繼續比較下一 組數據，而left 指針不變

（因為他還是可以去匹配比 nums[right] 更小的數的）。

---

2.2.2 代碼編寫

---

2.2.3 題目總結

總結