企业官网建设流程全解析

一、有效三角形的个数

1.题目

2.核心思路

三角形三边条件：对于三条边 (a,b,c)，需要满足 (a+b>c,a+c>b,b+c>a)。 先将数组升序排序。排序后固定nums[tar]作为最长边，此时 (nums[tar]) 是三元组里最大值，自动满足 (a+nums[tar]>b)、(b+nums[tar]>a)，只需要满足 (a+b>nums[tar]) 即可构成三角形。

采用双指针：

left初始在区间最左端（最小数），right在tar-1（最长边前一位）

如果(nums[left]+nums[right] > nums[tar])：说明从left到right-1的所有数，和nums[right]配对，都满足条件。一共有right-left组，直接加到答案；然后right--，尝试更小的右边界。

如果 (nums[left]+nums[right] < nums[tar])：两数之和不够大，left++，增大左值。

外层循环：tar从数组末尾向前枚举，直到tar >= 2（至少需要另外两个元素）。

3.举例模拟

示例：nums = [2,2,3,4]排序后：[2,2,3,4]，\(n=4\)，ret=0

tar=3（nums[tar]=4），left=0，right=2

left=0, right=2：nums[0]+nums[2] = 2+3 >4 → ret += 2-0 = 2，ret=2；right=1

left=0, right=1：nums [0]+nums [1]=2+2 >4？4>4 不成立 → left++，left=1。此时 left 不小于 right，本轮 tar 循环结束。

tar=2（nums[tar]=3），left=0，right=1

left=0, right=1：nums [0]+nums [1]=2+2>3 → ret +=1-0=1，ret=3；right=0，循环结束。

tar=1 不满足 tar>=2，外层循环结束。 最终答案 ret=3。

合法三元组：(2,2,3)、(2,3,4)、(2,3,4)，共 3 组。

4.代码参考

5..复杂度

时间复杂度：(O(n^2)) 排序：(O(nlog n))；外层 for 循环最多n次，内层 while 双指针每个 tar 最多遍历一次，内层总复杂度(O(n))，整体(O(n^2))，(nlog n)可以忽略。

空间复杂度：(O(log n)) 排序使用的栈开销；没有额外开辟数组，仅常数个变量。原地排序。

二、两数之和

1.题目

2.核心思路

给定升序有序数组，寻找两个元素，相加等于目标值target。 设置左右双指针：

left指向数组最左端（最小元素），right指向数组最右端（最大元素）

若price[left]+price[right] < target：总和太小，左指针右移，增大和；

若price[left]+price[right] > target：总和太大，右指针左移，减小和；

若等于 target：直接返回这两个数；

当left >= right还没找到，说明不存在，返回{-1,-1}。

3.举例模拟

示例：price = [2,7,11,15], target = 9left=0，right=3

sum=2+15=17 >9 → right-- → right=2

sum=2+11=13 >9 → right-- → right=1

sum=2+7=9 == target → 返回[2,7]

4.代码参考

5..复杂度

时间复杂度：(O(n))。左右指针最多各移动 n 次，一次遍历。

注意：如果原始数组无序，需要先 sort 排序，排序会带来\(O(n\log n)\)开销。

空间复杂度：(O(1))，只使用常数额外变量。

三、三数之和

1.题目

2.核心思路

1. 排序：先把数组升序排序。排序后方便双指针移动，同时方便跳过重复元素。
2. 固定第一个数 nums [a]：循环枚举 a，目标：找nums[left]+nums[right] = -nums[a]（记为 tar）。
3. a 去重：如果当前nums[a]和前一个nums[a-1]相等，直接 continue，避免重复三元组。
4. 双指针：left=a+1，right=nums.size()-1
   • nums[left]+nums[right] == tar：找到一组解，存入结果；然后跳过 left、right 侧重复数字，再left++,right--
   • nums[left]+nums[right] < tar：和太小，left 右移增大和
   • nums[left]+nums[right] > tar：和太大，right 左移减小和
5. 收集所有不重复三元组返回。

3.举例模拟

输入：nums = [-1,0,1,2,-1,-4]排序后：[-4,-1,-1,0,1,2]，ret 初始为空

1. a=0，nums [a]=-4，tar=4；left=1 (-1), right=5 (2) sum=-1+2=1 <4 → left++ → left=2 (-1), sum=-1+2=1<4 → left++ → left=3 (0), sum=0+2=2<4 → left++ → left=4 (1), sum=1+2=3<4 → left++，left 不再 < right，本轮无结果。

2. a=1，nums [a]=-1，tar=1；left=2 (-1), right=5 (2) sum=-1+2=1 == tar。存入[-1,-1,2]left 去重：nums [2]==nums [3]？ -1≠0，不进入循环 right 去重：nums [5]==nums [4]？2≠1，不进入循环 left++,right-- → left=3，right=4 现在 left<right：sum=0+1=1 == tar。存入[-1,0,1]left 去重：nums [3]==nums [4]？0≠1 right 去重：nums [4]==nums [3]？1≠0 left++,right--，left>=right，本轮结束。

3. a=2：nums [a]=-1，a>0 且 nums [a]==nums [a-1](-1 == -1)，continue 跳过。

4. a=3：nums.size()-2=4，a=3 <4，nums [a]=0，tar=0；left=4，right=5，sum=1+2>0，right--，left>=right，无结果。 循环结束。 结果：[[-1,-1,2],[-1,0,1]]

4.代码参考

5..复杂度

时间复杂度：(O(n^2)) 排序：(O(nlog n))；外层 for 循环 n 次，内层双指针最多 O (n)；(O(nlog n)+O(n^2)=O(n^2))。

空间复杂度：(O(log n)) 排序需要(log n)栈空间；结果数组不计入额外空间开销。

四、四数之和

1.题目

2.核心思路

排序 + 两层循环固定前两个数 (a,b) + 双指针 (c,d) 找后两个数

1.先把数组排序：方便去重和双指针移动。

2.外层循环a：固定第 1 个数，跳过重复 a，避免重复四元组； 目标：剩下三个数之和 =tar1 = target - nums[a]

3.内层循环b：固定第 2 个数，从a+1开始，跳过重复 b； 目标：剩下两个数之和 =tar2 = tar1 - nums[b]

4.双指针c = b+1（左），d = n-1（右），在b右侧区间寻找两数之和等于tar2：

nums[c]+nums[d] == tar2：找到一组解，存入答案；然后跳过 c、d 位置的重复元素，再收缩指针c++,d--

和偏小：c++，增大总和

和偏大：d--，减小总和

5.使用long long：防止 int 数值相加溢出。

6.本质：把4 数之和降维成3 数之和，再降维成2 数之和（双指针）。

3.举例模拟

样例：nums = [1,0,-1,0,-2,2], target = 0排序后：[-2,-1,0,0,1,2]，n=6 目标：找 4 个数相加等于 0。

1.a=0，nums [a]=-2 tar1 = 0 - (-2) = 2 b 从 a+1=1 开始：

b=1，nums [b]=-1，tar2 = 2 - (-1)=3 c=2，d=5：nums [c]=0，nums [d]=2，sum=2 <3 → c++ c=3，d=5：sum=0+2=2<3 → c++ c=4,d=5：sum=1+2=3 == tar2 存入[-2,-1,1,2]；c、d 去重，c++,d--，c 不再小于 d，双指针结束。

b=2，nums [b]=0，tar2=2-0=2 c=3,d=5：nums [3]=0,nums [5]=2 sum=2 == tar2 存入[-2,0,0,2]；c++,d--，循环结束。

b=3，nums[b]=0，b>a+1 && nums[b]==nums[b-1]→ 重复，continue。

2.a=1，nums [a]=-1 a>0 && nums [a]==nums [a-1]？nums [-1]=-2≠-1，不跳过。 tar1 = 0 - (-1)=1 b 从 a+1=2 开始：

b=2，nums [b]=0，tar2=1-0=1 c=3,d=5：nums [3]=0,nums [5]=2 sum=2>1 → d-- c=3,d=4：0+1=1 == tar2 存入[-1,0,0,1]；c++,d--，循环结束。

3.a=2，nums[a]=0，a>0 && nums[a]==nums[a-1]nums [1]=-1≠0，但是 a<n-3 → a=2，n-3=3，a=2 满足；后续 b 循环找不到新解。

4.a=3：a<n-3→ 3<3 不成立，外层循环结束。

最终结果：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

4.代码参考

5.复杂度

时间复杂度：(O(n^3)) 排序：(O(nlog n))；两层循环 a,b 是(O(n^2))，内部双指针 c,d 最多遍历一次数组(O(n))；总的是 (O(n^3))。

四数之和最优就是(O(n^3))，无法到(O(n^2))。

空间复杂度：(O(log n)) 排序需要栈空间；不计保存答案的 ret 数组，额外空间为排序栈空间。

五、总结

共性

前提：数组排序，是双指针、去重的基础；

核心思想：固定一部分，双指针在剩余区间相向收缩，把暴力多层枚举降低复杂度；

相向双指针适用场景：有序数组，判断两数之和和目标值的大小关系，通过移动左右指针调整总和。

四个题对比

1. 有序数组两数之和

做法：left=0，right=n-1，相向移动

目标：nums[left]+nums[right]==target

特点：不涉及去重，只找一组解；无序数组直接用哈希表更方便

2. 三数之和

做法：固定 a，双指针left=a+1, right=n-1，找两数之和等于-nums[a]

关键点：a、left、right 去重，防止重复三元组

3. 四数之和

做法：固定 a、b 两层循环，双指针c=b+1,d=n-1找两数之和

关键点：a、b 去重；必须 long long 防 int 溢出

4. 有效三角形的个数（特殊相向双指针）

思路：排序后固定最长边 tar，只需要判断短两边之和 > 最长边，其余两个三角形条件自动成立

技巧：满足条件时一次性批量计数（right-left 组），不用逐个枚举，效率更高