★ 算法OJ题 ★ 力扣18

★ 算法OJ题 ★ 力扣18 - 四数之和

2024-09-03 06:28

文章标签 算法力扣 18 四数 oj

本文主要是介绍★ 算法OJ题 ★ 力扣18 - 四数之和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Ciallo～(∠・ω< )⌒☆ ~ 今天，爱丽速子将和大家一起做一道双指针算法题--四数之和~

一题目

二算法解析

三编写算法

做此题前最好先看一下前两篇博客~：

★ 算法OJ题 ★ 力扣 LCR179 - 和为 s 的两个数字-CSDN博客

★ 算法OJ题 ★ 力扣15 - 三数之和-CSDN博客

一题目

18. 四数之和 - 力扣（LeetCode）

二算法解析

解法一：排序 + 暴力枚举 + 利用set去重

时间复杂度：O(N ^ 4)

解法二：排序 + 双指针

算法思路：

1. 依次固定一个数 a；

2. 在这个数 a 的后面区间上，利⽤三数之和找到三个数，使这三个数的和等于 target - a 即可。

2.1 依次固定一个数 b；
2.2 在这个数 b 的后⾯区间上，利⽤双指针找到两个数，使这两个数的和等于 target - a - b 即可。

这道题里面需要有去重操作~

找到⼀个结果之后， left 和 right 指针要跳过重复的元素；
当使⽤完⼀次双指针算法之后，固定的 a，b 也要跳过重复的元素。

三编写算法

三个for循环，时间复杂度O(N^3)

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {sort(nums.begin(), nums.end()); // 排序vector<vector<int>> ret; // 存放结果的顺序表~int n = nums.size();for(int i = 0; i < n; ) // 固定数a{for(int j = i + 1; j < n; ) // 固定数b{int left = j + 1, right = n - 1;long long aim = (long long)target - nums[i] - nums[j];while(left < right){int sum = nums[left] + nums[right];if(sum == aim){ret.push_back({ nums[i], nums[j], nums[left], nums[right] });left++;right--;// 去重，left right 跳过相同数，但不能越界while(left < right && nums[left] == nums[left - 1])left++;while(left < right && nums[right] == nums[right + 1])right--;}if(sum < aim)left++;if(sum > aim)right--;}j++;// 去重，j 跳过相同数，但不能越界while(j < n && nums[j] == nums[j - 1])j++;}i++;// 去重，i 跳过相同数，但不能越界while(i < n && nums[i] == nums[i - 1])i++;}return ret;}
};