【leetcode刷题】：双指针篇（有效三角形的个数、和为s的两个数）

一、有效三角形的个数

题目解析

有效三角形的个数【点击跳转】

题目意思很好理解：就是在一堆非负整数的数组里，随机选三个数进行搭配，然后统计这个数组中任意三个数能组成三角形的组合个数。

注意： 判断任意三个数是否能组成三角形的条件是 任意 两个数相加大于第三个数。

【示例一】：
输入: nums = [2,2,3,4]
输出: 3
四个数选三个数总共有四种情况

情况一：2 2 3 （任意两个数大于第三个数）满足题意
情况二：2 2 4 （2 + 2等于四）不满足题意
情况三：2 3 4 （任意两个数大于第三个数）满足题意
情况四：2 3 4 （任意两个数大于第三个数）满足题意

可以组成三个三角形，所以输出为3

【示例二】：
输入: nums = [4,2,3,4]
输出: 4
四个数选三个数总共有四种情况

情况一：4 2 3 （任意两个数大于第三个数）满足题意
情况二：4 2 4 （任意两个数大于第三个数）满足题意
情况三：4 3 4 （任意两个数大于第三个数）满足题意
情况四：2 3 4 （任意两个数大于第三个数）满足题意

可以组成四个三角形，所以输出为4

算法原理

解法一：暴力枚举（超时）
将所有的情况全部枚举出来，然后统计符合题意的情况。
暴力枚举代码：

// 暴力枚举
class Solution {
public:int triangleNumber(vector<int>& nums) {int count = 0;// 固定第一个数for(int i = 0; i < nums.size(); i++){// 固定第二个数for(int j = i + 1; j < nums.size(); j++){// 固定第三个数for(int k = j + 1; k < nums.size(); k++){if((nums[i] + nums[j] > nums[k]) && (nums[i] + nums[k] > nums[j]) && (nums[j] + nums[k] > nums[i]))count++;}}}return count;}
};

解法二：排序 + 双指针
首先根据题目的意思是数组里的元素都是大于等于零的，这里我们就可以利用组成三角形的一个特性：

假设三个数a、b、c，最大数是c，那么：

• 1、a + c > b
• 2、b + c > a
• 3、a + b > c
  这是判断是否能构成三角形的条件

其实第一种和第二种情况可以合并成一种情况，因为c是最大的那个数，一个最大的数加一个大于零的数，其结果一定是大于另外一个数的

知道了这个特性，我们的算法就有了优化的空间。

我们可以先给数组里的元素排个序，先固定一个最大的数，然后利用双指针算法结合上面讲的特性来优化算法：

根据上面的图可以看到，最大的数是13，然后会有下面这几种情况：

• 情况一：nums[left] + nums[right] > c
• 情况二：nums[left] + nums[right] <= c 小于和等于属于同一种情况，即不能构成三角形

根据单调性，假设是情况一，因为left往右的数都是比left大的数，left加上right已经大于最大的数了，那么一个大于left的数加上right，那必定是大于最大的数c的，所以left往右就没必要计算了，因为left与right这个区间再加上最大数构成的三个数一定是能构成三角形的，能构成三角形的个数就是right - left，接下来的操作就是要right往左移，然后继续判断

假设是情况二，left加上right是小于最大值c的，那么right往左的数与left相加也一定是小于最大数c，所以接下来的操作是要left往右移，然后继续判断。

最后双指针判断结束后，只需要更新最大值（最大值往左移），然后重新利用双指针进行判断。

代码编写

C++代码：

class Solution {
public:int triangleNumber(vector<int>& nums) {// 排序sort(nums.begin(), nums.end());int n = nums.size(), ret = 0;// 固定最大数for(int i = n - 1; i >= 2; i--){int left = 0, right = i - 1;while(left < right){if(nums[left] + nums[right] > nums[i]){ret += right - left;right--;}else{left++;}}}return ret;}
};

C语言代码：

// 比较函数
int cmpfunc (const void * a, const void * b)
{return ( *(int*)a - *(int*)b );
}int triangleNumber(int* nums, int numsSize) {// 排序qsort(nums, numsSize, sizeof(int), cmpfunc);int ret = 0;// 固定最大数for(int i = numsSize - 1; i >= 2; i--){int left = 0, right = i - 1;while(left < right){if(nums[left] + nums[right] > nums[i]){ret += right - left;right--;}else{left++;}}}return ret;
}

Python代码：

class Solution:def triangleNumber(self, nums: List[int]) -> int:# 排序nums.sort()ret = 0# 固定最大数for i in range(len(nums) - 1, 1, -1):left, right = 0, i - 1while left < right:if nums[left] + nums[right] > nums[i]:ret += right - leftright -= 1else:left += 1return ret

二、和为s的两个数

题目解析

和为s的两个数【点击跳转】

题目的大意就是给你一个递增的数组，然后找到两个数相加等于目标值，然后返回这两个数，返回的这两个数顺序随意。

算法原理

解法一：暴力枚举（超时）
直接两层for循环将所有的可能全部枚举出来，然后找到两个数相加等于目标值的两个数，直接返回。

暴力枚举C++代码：

class Solution {
public:vector<int> twoSum(vector<int>& price, int target) {// 固定第一个数for(int i = 0; i < price.size(); i++){// 固定第二个数for(int j = i + 1; j < price.size(); j++){if(price[i] + price[j] == target)// 这里是隐式类型转换，可以转换成vector<int>类型return {price[i], price[j]};}}// 满足力扣的要求，这里的值可随意返回return {-1, -1};}
};

解法二：双指针
在暴力枚举的时候我们忽略了一个很重要的因素，那就是这个数组里的元素是单调递增的，只要是单调递增的数组，我们就可以大胆的利用双指针算法来解决问题。

1、第一种情况：sum = price[left] + price[right] > target 如果sum大于我们的目标值target，由于数组是单调递增的，price[left]已经是最小的值了，price[right]是数组中最大的那个数。一个最小的值加上一个最大的值最后大于目标值，而且left往后的值都是大于left的(数组递增)，所以我们的操作就只要让right往左移就可以了。

2、第二种情况：sum = price[left] + price[right] < target 相加后的结果小于目标值target，说明left小了(right左边的值都是小于right的)，所以我们的操作只需要让left向右移动即可。

3、第三种情况：sum = price[left] + price[right] == target 相加后的结果是等于目标值target，满足题目要求，直接结果即可。

相比于解法一的暴力解法，利用数组的单调递增的双指针解法效率更高，我们可以分析一下两种解法的时间复杂度对比。
$$\begin{gathered} \text{暴力解法：}O(N^2) \\ \text{双指针：}O(N) \end{gathered}$$
可以看到时间复杂度直接优化了一个量级，说明我们的算法是比较优秀的算法了。

代码编写

C++代码：

class Solution {
public:vector<int> twoSum(vector<int>& price, int target) {int n = price.size();// 定义左右双指针int left = 0, right = n - 1;while(left < right){// sum > targetif(price[left] + price[right] > target)right--;// sum < targetelse if(price[left] + price[right] < target)left++;// sum == targetelsereturn {price[left], price[right]};}return {-1, -1};}
};

C语言代码：

/*** Note: The returned array must be malloced, assume caller calls free().*/
int* twoSum(int* price, int priceSize, int target, int* returnSize) {// 定义左右双指针int left = 0, right = priceSize - 1;*returnSize = 2;  // 输出型参数int *ret = (int*)malloc(*returnSize * sizeof(int));while(left < right){// sum > targetif(price[left] + price[right] > target)right--;// sum < targetelse if(price[left] + price[right] < target)left++;// sum == targetelse{ret[0] = price[left], ret[1] = price[right];return ret;}}// 释放空间free(ret);ret = NULL;return NULL;
}

Python代码：

class Solution:def twoSum(self, price: List[int], target: int) -> List[int]:# 定义左右双指针left, right = 0, len(price) - 1while left < right:# sum > targetif price[left] + price[right] > target:right -= 1# sum < targetelif price[left] + price[right] < target:left += 1# sum == targetelse:return [price[left], price[right]]return [-1, -1]