本文属于个人记录基础算法刷题学习的记录，学习来源代码随想录，想学习基础算法的同学强烈推荐去看看学习，还有书籍。
1.数组
1.贪心
1.分割字符问题(新手)
题目：在一个 平衡字符串 中，‘L’ 和 ‘R’ 字符的数量是相同的。
给你一个平衡字符串 s，请你将它分割成尽可能多的平衡字符串。
注意：分割得到的每个字符串都必须是平衡字符串。
返回可以通过分割得到的平衡字符串的 最大数量 。
示例：输入：s = "RLRRLLRLRL"
输出：4
解释：s 可以分割为 "RL"、"RRLL"、"RL"、"RL" ，每个子字符串中都包含相同数量的 'L' 和 'R' 。
代码：
int check(char s)
{
int abs = 0, count = 0;
for(int i = 0; i < s.size(); i++)
{
if(s[i] == 'R')count ++;
else count--;
if(count == 0)abs++;
}
return abs;
}
2.翻硬币问题(简单)
现在有一个初始状态的硬币序列，还有一个目的状态的硬币序列，分别用#和%来表示正反，每次翻硬币只能翻两个挨着的硬币，怎样在短的次数内将初始态翻到目的状态？
初始态： # % % % % # % % % % % # % % # % % % # % % %
目的态： % % % % % % % % % % % # % % % # % % # % % %
次数：5次 次数：1次
分析：最短的次数其实就是第一个1/0状态和第二个对应的1/0状态下标之差，所以只要记录每次差然后相加就好了。
int main()
{
int sum = 0, k;
while(scanf("%s %s", a, b) != EOF)
{
int n= strlen(a);
bool flag = true;
for(int i = 0; i < n; i++)
{
if(a[i] != b[i])
{
if(flag)
{
flag = false;//状态不同就变一个状态
k = i;
}
else
{
flag = true;
sum += i - k; //i - k是第一对同状态的下标的距离
}
}
}
}
cout << sum;
}
2.排序
1.基础快速排序
数字排序
void quick_sort( int q[], int l, int r)
{
if(l >= r)return;
int i = l - 1, j = r + 1, x = q[(l + r) / 2] ;
while(i < j)
{
do i++;while(q[i] < x);
do j--;while(q[j] > x);
if(i < j)swap(q[i], q[j]);
}
quick_sort(q, l , j);
quick_sort(q, j + 1, r);
}
2.归并排序
1.基础归并排序
void marge_sort(int b[], int l, int r)//归并排序
{
if (l >= r)return; //如果只有一个数或者没有，则返回
int mid = l + r >> 1; //定一个判断中间值
marge_sort(b, l, mid), marge_sort(b, mid + 1, r); //调用函数，一个是边界的左边，一个是边界的右边
int k = 0, i = l, j = mid + 1; //开始定义移动指针，进行移动
while (i <= mid && j <= r) //循环判断开始交换大小值
{
if (b[i] <= b[j])tem[k++] = b[i++];
else tem[k++] = b[j++];
}
while (i <= mid)tem[k++] = b[i++]; //开始拼接
while (j <= r)tem[k++] = b[j++]; //开始拼接
for (i = l, j = 0; i <= r; i++, j++)b[i] = tem[j]; //将tem数组的值覆盖到b数组中去
}
2.应用1：求逆序对
ll marge_sort(int l , int r)
{
if(l >= r)return;
int mid = l + r >> 1;
ll res = marge_sort(l, mid) + marge_sort(mid + 1, r);
int k = 0, i = l, j = mid + 1;
while(i <= mid && j <= r)
{
if(a[i] <= a[j])temp[k++] = a[i++];
else
{
temp[k++] = a[j++];
res += mid - i + 1;
}
}
while(l <= mid)temp[k++] = a[i++];
while(j <= r)temp[k++] = a[j++];
for(int i = l, j = 0; i <= r; i++, j++)a[i] = temp[j];
return res;
}
3.双指针
一般使用两个指针移动来解决序列问题维护一段区间，在两端区间合并类等问题
for(int i = 0, j = 0; i < n; i++)
{
while((j < i && check( i, j))
//具体的逻辑问题
}
1.最长不重复序列长度
在某一段序列中，求出在其中最长的某一段的序列长度是多少？
//a[] 是序列， b[] 记录序列中的数字出现的次数， res是最长的长度
void check(int n)
{
for(int i = 0,j = 0; i < n; i++)
{
b[a[i]] ++;
while(b[a[i]] > 1)
{
b[a[j]] --;
j++;
}
}
res = max(res, i - j + 1);
}
2.移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。
示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。你不需要考虑数组中超出新长度后面的元素。
class Solution{
public:
int remove(vector<int>&nums, int target)
{
int s = 0;
for(int f = 0; f < nums.size(); f++)
{
if(target != nums[f])nums[s++] = nums[f];
}
return s;
}
};
3.删除有序数组中的重复项
给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
class Solution{
public:
int remove(vector<int>&nums)
{
int f = 1, s = 1;
if(nums.size() == 0)return 0;
while(f < nums.size())
{
if(nums[f] != nums[f - 1])
{
nums[s++] = nums[f];
}
f++;
}
return s;
}
}
4.移除0
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
//法一
class Solution{
public:
int remove(vector<int>&nums)
{
//思想和移除元素类似，先清除再赋值，不灵活
int f = 0, s = 0;
if(nums.size() == 0)return ;
while(f < nums.size())
{
if(nums[f] != 0)nums[s++] = nums[f];
f++;
}
while(s < nums.size())nums[s++] = 0;
}
}；
//法二
//交换值，在不是0的时候，s和f指针进度一致，但是在出现了0之后，开始一直前后交换
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int s = 0, f = 0;
if(nums.size() == 0)return ;
while(f < nums.size())
{
if(nums[f] != 0)
{
int temp;
temp = nums[f];
nums[f] = nums[s];
nums[s++] = temp;
}
f++;
}
}
};
//法三：优化
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int s = 0, f = 0;
if(nums.size() == 0)return ;
while(f < nums.size())
{
if(nums[f] != 0)
{
if(f > s)
{
nums[s] = nums[f];
nums[f] = 0;
}
s++;
}
f++;
}
}
};
5.比较含退格的字符串
给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，请你判断二者是否相等。# 代表退格字符。
如果相等，返回 true ；否则，返回 false 。
注意：如果对空文本输入退格字符，文本继续为空。
class Solution {
public:
bool backspaceCompare(string s, string t) {
int i = s.length() - 1, j = t.length() - 1;
int ii = 0, jj = 0;
while(i >= 0 || j >= 0)
{
while(i >= 0)
{
if(s[i] == '#')ii++, i--;
else if(ii > 0)ii--, i--;
else break;
}
while(j >= 0)
{
if(t[j] == '#')jj++, j--;
else if(jj > 0)jj--, j--;
else break;
}
if(i >= 0 && j >= 0)
{
if(s[i] != t[j])return false;
}
else
{
if(i >=0 ||j >= 0)return false;
}
j--, i--;
}
return true;
}
};
6.有序数组的平方
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
思想：双指针i，j分别从头尾进行，因为他是一个有序的数组。-
class Solution{
public:
int check(vector<int> & nums)
{
int i = 0, j = nums.size() - 1, k = nums.size() - 1;
vector<int>a(nums.size(), 0);
while(i <= j)
{
if(nums[i] * nums[i] > nums[j] * nums[j])a[k--] = nums[i] * nums[i]; i++;
else a[k--] = nums[j] * nums[j]; j--;
}
return a;
}
};
4.二分
知识详解
关于二分的知识涉及到一个最核心的问题就是边界问题，在什么时候的边界是如何去处理的？
首先我们需要明白区间有两种区间，一种是左闭右闭，还有一种是左闭右开。那么其中有什么区别呢？
当我们遇到左闭右闭的区间的时候，
1.[left,right]:left = 0, right = nums.size() - 1;双闭区间
while(l <= r)
{
int mid = l + r >> 1;
if(nums[mid] > target)r = mid - 1;
else if(nums[mid] < target)l = mid;
else return l;
}
2.[left,righht):left = 0, right = nums.size(); 单闭区间
while(l < r)
{
int mid = l + r >> 1;
if(nums[mid] > target)r = mid;
else if(nums[mid] < target)l = mid + 1;
else return l;
}
1.整数二分
一般使用二分能够在一定程度上减少时间复杂度，在不附加的情况下，时间复杂度为O(log N),在使用二分知识解题的基础之上，要注意一个问题就是在有序的序列上来进行分割，其中我们会遇到一个问题就是边界问题，左边界还是右边界的问题，在哪一种情况下使用哪一种求边界的问题？
1.查找出该数字的是否存在
// 1.寻找左边界第一个数字
// a[]是数组， n是查找数字， m是查询次数
void FindL(int a[], n, m)
{
while(m --)
{
int l = 0, r = n - 1;
while(l < r)
{
int mid = (l + r) >> 1;
if(a[mid] >= n)r = mid;
else l = mid + 1;
}
}
if(a[l] == n)cout << "find" << endl;
}
//2.寻找右边界的数字
void FindL(int a[], n, m)
{
while(m --)
{
int l = 0, r = n - 1;
while(l < r)
{
int mid = (l + r + 1) >> 1;//注意寻找右边界的时候，范围加1
if(a[mid] <= n)l = mid;
else r = mid - 1;
}
}
if(a[l] == n)cout << "find" << endl;
}
2.浮点数二分
1.求三次方根
给定一个浮点数 n，求它的三次方根?
void find()
{
double n;
cin >> n;
d l = -1000, r = 1000;
while(r - l > 1e-8)
{
double mid = l + r >> 1;
if(mid * mid *mid > n)r = mid;
else l = mid;
}
printf("%lf", l);
}
5.前缀和与差分
1.前缀和
1.询问前缀和
输入一个长度为n的整数序列。
接下来再输入m个询问，每个询问输入一对L, R。
对于每个询问，输出原序列中从第L个数到第R个数的和。
cin >> n >> m;
for(int i = 0; i < n; i++)cin >> a[i];
for(int i = 0; i < n; i++)s[i] = s[i - 1] + a[i];//求出前缀和
while(m--)
{
int l, r;
cin >> l >> r;
cout << s[r - 1] - s[l - 2] << endl;//区间之和等于大区间减去小区间
}
2.差分
6.DFS和BFS
1.DFS
2.BFS
7.数组
8.滑动窗口
1.长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。
示例：
输入：s = 7, nums = [2,3,1,2,4,3] 输出：2 解释：子数组 [4,3] 是该条件下的长度最小的子数组
一般使用暴力解法或者是滑动窗口，本题类似于双指针知识。
法一：暴力解法
class Solution {
public:
int minSubArrayLen(int s, vector<int>& nums) {
int result = INT32_MAX; // 最终的结果
int sum = 0; // 子序列的数值之和
int subLength = 0; // 子序列的长度
for (int i = 0; i < nums.size(); i++) { // 设置子序列起点为i
sum = 0;
for (int j = i; j < nums.size(); j++) { // 设置子序列终止位置为j
sum += nums[j];
if (sum >= s) { // 一旦发现子序列和超过了s，更新result
subLength = j - i + 1; // 取子序列的长度
result = result < subLength ? result : subLength;
break; // 因为我们是找符合条件最短的子序列，所以一旦符合条件就break
}
}
}
// 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
return result == INT32_MAX ? 0 : result;
}
};
法二：滑动窗口
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int res = INT32_MAX;
int i = 0, j =0, sum = 0,leng = 0;
for(int j = 0; j < nums.size(); j++)
{
sum += nums[j];
while(sum >= target)
{
leng = j - i + 1;
res = res < leng ? res : leng;
sum = sum - nums[i++];
}
}
return res == INT32_MAX ? 0 : res;
}
};
### 2.水果篮子
在一排树中，第 i 棵树产生 tree[i] 型的水果。
你可以从你选择的任何树开始，然后重复执行以下步骤：
把这棵树上的水果放进你的篮子里。如果你做不到，就停下来。
移动到当前树右侧的下一棵树。如果右边没有树，就停下来。
请注意，在选择一颗树后，你没有任何选择：你必须执行步骤 1，然后执行步骤 2，然后返回步骤 1，然后执行步骤 2，依此类推，直至停止。
你有两个篮子，每个篮子可以携带任何数量的水果，但你希望每个篮子只携带一种类型的水果。
用这个程序你能收集的水果树的最大总量是多少？
输入：[0,1,2,2]
输出：3
解释：我们可以收集 [1,2,2]
如果我们从第一棵树开始，我们将只能收集到 [0, 1]。
使用双指针和滑动窗口的知识，erase()是C++中一种挪动删除数组中某种字符的函数。
```c
class Solution
{
public:
int totalFruit(vector<int>& fruits) {
unordered_map<int , int>a;
int n = 2;
int res = 0;
for(int i = 0, j = 0; j < fruits.size(); j++)
{
a[fruits[j]]++;
while(a.size() > n)
{
a[fruits[i]]--;
if(a[fruits[i]] == 0)
{
a.erase(fruits[i]);
}
i++;
}
res = max(res, j - i + 1);
}
return res;
}
};
9.螺旋矩阵
给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
// 创建二维矩阵
vector<vector<int>> matrix(n);
for (int i = 0; i < matrix.size(); i++)
matrix[i].resize(n);
// 上下左右
int u = 0;
int d = n-1;
int l = 0;
int r = n-1;
int num = 1;
while(true){
// 上
for(int i=l; i <= r; i++) matrix[u][i] = num++;
if (u++ >= d) break;
// 右
for(int i=u; i <= d; i++) matrix[i][r] = num++;
if (r-- <= l) break;
// 下
for(int i=r; i >= l; i--) matrix[d][i] = num++;
if (d-- <= u) break;
// 左
for(int i=d; i >= u; i--) matrix[i][l] = num++;
if (l++ >= r) break;
}
return matrix;
}
};
2.哈希表
2.有效的字母异位词
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
示例 1: 输入: s = “anagram”, t = “nagaram” 输出: true
示例 2: 输入: s = “rat”, t = “car” 输出: false
说明: 你可以假设字符串只包含小写字母。
分析：使用哈希表，对比字母一共26个，开辟26个数组空间，每一个字母对比一个空间，第一次遍历s，对应字母++，第二次遍历t，对应字母–。
在最后遍历一遍开辟的空间，如果有存在的数字，则不同。
class Solution {
public:
bool isAnagram(string s, string t) {
int rec[26] = {0};
for(int i = 0; i < s.size(); i++)
{
rec[s[i] - 'a']++;
}
for(int i = 0; i < t.size(); i++)
{
rec[t[i] - 'a']--;
}
for(int i = 0; i < 26; i++)
{
if(rec[i] != 0)return false;
}
return true;
}
};
class Solution {
public boolean isAnagram(String s, String t) {
int [] aa = new int[26];
for(char c : s.toCharArray()){
aa[c - 'a']++;
}
for(char c : t.toCharArray()){
aa[c - 'a']--;
}
for(int i = 0; i < 26; i++){
if(aa[i] != 0)return false;
}
return
}
}
3.赎金信
给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
如果可以，返回 true ；否则返回 false 。
magazine 中的每个字符只能在 ransomNote 中使用一次。
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
int [] aa = new int[26];
for(char c : magazine.toCharArray()){
aa[c - 'a']++;
}
for(char c : ransomNote.toCharArray()){
aa[c - 'a']--;
}
for(int i = 0; i < 26; i++){
if(aa[i] < 0)return false;
}
return true;
}
}
4.有效的字母异位词组
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
//判断是否为空字符串数组
if(strs == null || strs.length == 0){
return new ArrayList();
}
//1.创建一个哈希表
Map<String,List> map = new HashMap<String, List>();
for (String s: strs) {
//将字符串转化为字符数组
char[] chars = s.toCharArray();
//对字符数组按照字母顺序排序
Arrays.sort(chars);
//将排序后的字符串作为哈希表中的key值
String key = String.valueOf(chars);
//2.判读哈希表中是否有该key值
if (!map.containsKey(key)){
//若不存在，则为新的异位词语，在map中创建新的键值对
map.put(key,new ArrayList());
}
//3.将该字符串放在对应key的list中
map.get(key).add(s);
}
//返回map中所有键值对象构成的list
return new ArrayList(map.values());
}
}
5.两个数组的交集
题意：给定两个数组，编写一个函数来计算它们的交集。
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
if(nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0){
return new int[0];
}//判断数组是否无交集
Set<Integer> str = new HashSet<>();
Set<Integer> restr = new HashSet<>();
for(int i : nums1){
str.add(i);
}//遍历数组一
for(int i : nums2){
if(str.contains(i)){
restr.add(i);
}
}//遍历数组二
int []a = new int[restr.size()];
int index = 0;
for(int i : restr){
a[index++] = i;
}//寻找重复的数组
return a;
}
}
重要知识点：
1.Set、HashSet的使用方法
HashSet()：
HashSet():构造一个新的空集合; 背景HashMap实例具有默认初始容量（16）和负载因子（0.75）。
HashSet(Collection? extends E> c) :构造一个包含指定集合中的元素的新集合。
HashSet(int initialCapacity) :构造一个新的空集合; 背景HashMap实例具有指定的初始容量和默认负载因子（0.75）。
HashSet(int initialCapacity, float loadFactor) :构造一个新的空集合; 背景HashMap实例具有指定的初始容量和指定的负载因子。
2.add和contains的使用方法
contains():如果此集合包含指定的元素，则返回true 。 更正式地，返回true当且仅当该集合包含元素e ，使得(onull ? enull : o.equals(e))
add():应该就是向集合里面增加元素
6.两个数组的交集||
给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。
class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
if (nums1.length > nums2.length) {
return intersect(nums2, nums1);
}
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int num : nums1) {
int count = map.getOrDefault(num, 0) + 1;
map.put(num, count);
}
int[] intersection = new int[nums1.length];
int index = 0;
for (int num : nums2) {
int count = map.getOrDefault(num, 0);
if (count > 0) {
intersection[index++] = num;
count--;
if (count > 0) {
map.put(num, count);
} else {
map.remove(num);
}
}
}
return Arrays.copyOfRange(intersection, 0, index);
}
}
其中关于Map的使用方法
1.getOrDefault
2.put
3.copyOfRange
4.remove
7.快乐数
class Solution {
public boolean isHappy(int n) {
Set<Integer> a = new HashSet<>();
while(n != 1 && !a.contains(n)){
a.add(n);
n = get(n);
}
return n == 1;
}
private int get(int n){
int num = 0;
while(n > 0){
int temp = n % 10;
num += temp * temp;
n /= 10;
}
return num;
}
}
8.两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
class Solution {
public int[] twoSum(int[] nums, int target) {
int []a = new int[2];
if(nums == null || nums.length == 0){
return a;
}
Map<Integer, Integer> map = new HashMap<>();
for(int i = 0; i < nums.length; i++){
int temp = target - nums[i];
if(map.containsKey(temp)){
a[0] = i;
a[1] = map.get(temp);
}
map.put(nums[i], i);
}
return a;
}
}
9.三个数之和
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
注意： 答案中不可以包含重复的三元组。
示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]
满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(nums);
for(int i = 0; i < nums.length; i++){
if(nums[i] > 0)return res;
if(i > 0 && nums[i] == nums[i - 1])continue;
int left = i + 1;
int right = nums.length - 1;
while(left < right){
int sum = nums[left] + nums[i] + nums[right];
if(sum > 0)right--;
else if(sum < 0)left++;
else {
res.add(Arrays.asList(nums[i], nums[left], nums[right]));
while(left < right && nums[left] == nums[left + 1])left++;
while(left < right && nums[right] == nums[right - 1])right--;
right--;
left++;
}
}
}
return res;
}
}
思路设计：《使用双指针》
拿这个nums数组来举例，首先将数组排序，然后有一层for循环，i从下标0的地方开始，同时定一个下标left 定义在i+1的位置上，定义下标right 在数组结尾的位置上。
依然还是在数组中找到 abc 使得a + b +c = 0，我们这里相当于 a = nums[i] b = nums[left] c = nums[right]。
接下来如何移动left 和right呢， 如果nums[i] + nums[left] + nums[right] > 0 就说明 此时三数之和大了，因为数组是排序后了，所以right下标就应该向左移动，这样才能让三数之和小一些。
如果 nums[i] + nums[left] + nums[right] < 0 说明 此时 三数之和小了，left 就向右移动，才能让三数之和大一些，直到left与right相遇为止。
10.四数之和
题意：给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：
答案中不可以包含重复的四元组。
示例： 给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。 满足要求的四元组集合为： [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(nums);
for(int i = 0; i < nums.length; i++){
if(i > 0 && nums[i - 1] == nums[i])continue;
for(int j = i + 1; j < nums.length; j++){
if(j > i + 1 && nums[j - 1] == nums[j])continue;
int left = j + 1;
int rigth = nums.length - 1;
while(left < rigth){
int sum = nums[i] + nums[j] + nums[left] + nums[rigth];
if(sum > target)rigth--;
else if(sum < target)left++;
else{
res.add(Arrays.asList(nums[i], nums[j],
nums[left], nums[rigth]));
while(left < rigth && nums[left] == nums[left + 1])left++;
while(left < rigth && nums[rigth] == nums[rigth - 1])rigth--;
left++;
rigth--;
}
}
}
}
return res;
}
}
思路分析:《双指针》
思路三数之和几乎一直，需要注意的是不在需要判断a[i] > 0了，因为此时的target值不再是0，当然三数之和为不零思路也是一致的，四数之和那么就还要需要一层循环来表示定值数，第一层循环表示定值数a[i]，第二层循环表示定制数a[j]。其他思路几乎和求三叔是一致的。