河曲县城乡建设管理局网站,管理系统官方网站,.net网站开发模板,鄂州门户网目录 有效三角形的个数
解题思路
C代码实现
和为s的两个数字
解题思路
C代码实现
三数之和
解题思路
C代码实现
四数之和
解题思路
C代码实现 有效三角形的个数
题目链接#xff1a;611. 有效三角形的个数题目描述#xff1a;给定一个包含非负整数的数组nums代码实现
和为s的两个数字
解题思路
C代码实现
三数之和
解题思路
C代码实现
四数之和
解题思路
C代码实现 有效三角形的个数
题目链接611. 有效三角形的个数题目描述给定一个包含非负整数的数组nums返回其中可以组成三角形三条边的三元组个数。 解题思路
首先对于三条边能否构成三角形其条件就是任意两边之和大于第三边或者任意两边之差小于第三边也就是说对于任意的正整数a、b、c如果a b c且a c b且b c a那么a、b、c就能构成三角形。但是用a、b、c运算3次有点过于冗余所以需要优化下。
假如a、b、c是有序的也就是a b c那么只需要判断a b c就能直到能否构成三角形因为a b c成立c是最大的数那么a c b和b c a必然成立。
解法一排序暴力求解
先排序然后用3层for循环枚举所有的三元组。判断是否能构成三角形。
class Solution {
public:int triangleNumber(vectorint nums) {// 1. 排序sort(nums.begin(), nums.end());int n nums.size(), ret 0;// 2. 从小到大枚举所有的三元组for (int i 0; i n; i) {for (int j i 1; j n; j) {for (int k j 1; k n; k) {// 当最小的两个边之和大于第三边的时候统计答案if (nums[i] nums[j] nums[k])ret;}}}return ret;}
};这样做时间复杂度是O(n ^ 3)必然会超时。
解法二排序双指针
先对数组排序固定一个最长边然后在比这条边小的有序数组种找出一个二元组使二元组之和大于这个最长边由于数组有序可以使用双指针。设最长边枚举到位置 i 区间 [left, right] 是 i 位置左边的区间也就是比它小的区间如果 nums[left] nums[right] nums[i]:说明 [left, right - 1] 区间上的所有元素均可以与 nums[right] 构成比 nums[i] 大的二元组。满足条件的有 right - left 种。此时 right 位置的元素的所有情况相当于全部考虑完毕right-- 进入下一轮判断。如果 nums[left] nums[right] nums[i]:说明 left 位置的元素不可能与 [left 1, right] 位置上的元素构成满足条件的二元组。left 位置的元素可以舍去left 进入下一轮循环。 C代码实现
class Solution {
public:int triangleNumber(vectorint nums) {// 1. 排序sort(nums.begin(), nums.end());//2.双指针int ret 0;for(int i nums.size() - 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;}
}; 时间复杂度O(n ^ 2)排序的时间复杂度为 O(n log n)之后每个元素使用双指针进行一次遍历时间复杂度为 O(n ^ 2)。
空间复杂度O(log n)排序的栈开销。
和为s的两个数字
题目链接剑指 Offer 57. 和为s的两个数字题目描述输入一个递增排序的数组和一个数字 s在数组中查找两个数使得它们的和正好是 s。如果有多对数字的和等于 s则输出任意一对即可。 解题思路
解法一暴力枚举
两层for循环列出所有数字的组合判断是否等于目标值。
class Solution {
public:vectorint twoSum(vectorint nums, int target) {int n nums.size();for (int i 0; i n; i) {for (int j i 1; j n; j) {if (nums[i] nums[j] target)return {nums[i], nums[j]};}}return {-1, -1};}
};解法二双指针
1.初始化left、right指向数组左右两端。
2.当left right执行循环。
3.若nums[left] nums[right] target说明找到结果直接返回
若nums[left] nums[right] target当前和小于目标值需要增大和left
若nums[left] nums[right] target当前和大于目标值需要减小和right--
C代码实现
class Solution {
public:vectorint twoSum(vectorint price, int target) {int left 0, right price.size() - 1;while(left right){if(price[left] price[right] target)right--;else if(price[left] price[right] target)left;elsebreak; }return {price[left], price[right]};}
};
时间复杂度O(n)
空间复杂度O(1)
三数之和
题目链接15. 三数之和题目描述给你一个整数数组 nums判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k同时还满足 nums[i] nums[j] nums[k] 0。请你返回所有和为 0 且不重复的三元组。
注意答案中不可以包含重复的三元组。 解题思路
解法排序双指针
这道题与双指针类似可以利用双指针思想来优化暴力枚举。
1.先排序
2.固定一个数a
3.然后在这个数后面的区间内使用双指针快速找到两个数之和等于 -a。
注意该题是需要有去重操作
1.找到一个结果后left 和 right 指针要跳过重复元素。
2.使用完一次双指针后固定的数a也要跳过重复的元素。
C代码实现
class Solution {
public:vectorvectorint threeSum(vectorint nums) {//1.去重sort(nums.begin(), nums.end());//2.双指针int n nums.size();vectorvectorint vv;for(int i 0; i n; i) //固定数{//使用完双指针后的去重操作while(i i n nums[i - 1] nums[i])i;if(i n) break;if(nums[i] 0) break; //小优化int left i 1, right n - 1;int sum -1 * nums[i];while(left right){if(nums[left] nums[right] sum)right--;else if(nums[left] nums[right] sum)left;else{vv.push_back({nums[i], nums[left], nums[right]});left, right--;//left和right跳过重复元素while(left right nums[right 1] nums[right])right--;while(left right nums[left - 1] nums[left])left;}}}return vv;}
};
时间复杂度O(n ^ 2)
空间复杂度O(log n)排序的栈开销
四数之和
题目链接18. 四数之和题目描述给你一个由 n 个整数组成的数组 nums和一个目标值 target。请你找出并返回满足下述全部条件且不重复的四元组[nums[a], nums[b], nums[c], nums[d]]若两个四元组元素一一对应则认为两个四元组重复 解题思路
解法排序双指针
这道题是三数之和的升级版解法是类似的注意去重操作就可以的。
1.排序。
2.依次固定一个数a。
3.在a后面的区间利用三数之和找到三个数使得三个数的和等于target - a即可。
C代码实现
class Solution {
public:vectorvectorint fourSum(vectorint nums, int target) {vectorvectorint ans;//1.排序sort(nums.begin(), nums.end());//2.利用双指针解决问题int n nums.size();for(int i 0; i n; i) //固定 a{//去重 awhile(i i n nums[i] nums[i - 1]) i;if(i n) break;//三数之和的做法for(int j i 1; j n; j) //固定 b{//去重 b while(j ! 1 j n j - 1 ! i nums[j] nums[j - 1])j;if(j n) break;int left j 1, right n - 1;long long sum (long long)target - nums[i] - nums[j];while(left right){if(nums[left] nums[right] sum)right--;else if(nums[left] nums[right] sum)left;else{ans.push_back({nums[i], nums[j], nums[left], nums[right]});left, right--;// 去重 left 和 rightwhile(left right nums[left] nums[left - 1])left;while(left right nums[right] nums[right 1])right--;} }} }return ans;}
};
时间复杂度O(n ^ 3)
空间复杂度O(log n)排序的栈开销 拜拜下期再见
摸鱼ing✨
