🌸个人主页:https://blog.csdn.net/2301_80050796?spm=1000.2115.3001.5343
🏵️热门专栏:🍕 Collection与数据结构 (91平均质量分)https://blog.csdn.net/2301_80050796/category_12621348.html?spm=1001.2014.3001.5482
🧀Java EE(94平均质量分) https://blog.csdn.net/2301_80050796/category_12643370.html?spm=1001.2014.3001.5482
🍭MySql数据库(93平均质量分)https://blog.csdn.net/2301_80050796/category_12629890.html?spm=1001.2014.3001.5482
🍬算法(97平均质量分)https://blog.csdn.net/2301_80050796/category_12676091.html?spm=1001.2014.3001.5482
感谢点赞与关注~~~
目录
- 1. 有效三角形的个数(难度:🔵2度)
- 2.两数之和(难度:🟢1度)
- 3. 三数之和(难度:🟠4度)
- 4.四数之和(难度:🔴5度)
1. 有效三角形的个数(难度:🔵2度)
OJ链接
- 题目描述
购物车内的商品价格按照升序记录于数组 price。请在购物车中找到两个商品的价格总和刚好是 target。若存在多种情况，返回任一结果即可。
示例 1：
输入：price = [3, 9, 12, 15], target = 18
输出：[3,15] 或者 [15,3]
示例 2：
输入：price = [8, 21, 27, 34, 52, 66], target = 61
输出：[27,34] 或者 [34,27]
- 算法原理
先将数组排序。
我们可以固定⼀个==「最⻓边」，然后在⽐这条边⼩的有序数组中找出⼀个⼆元组==，使这个⼆元组之和⼤于这个最⻓边。由于数组是有序的，我们可以利⽤「对撞指针」来优化。
设最⻓边枚举到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++ 进⼊下轮循环
- 如果nums[left] + nums[right] > nums[i] ：
- 代码编写
class Solution {
public int triangleNumber(int[] nums) {
Arrays.sort(nums);
int ret = 0;
for (int n = nums.length-1;n >= 2;n--){//n固定最大边
int left = 0;
int right = n-1;
while (left < right){
if (nums[left] + nums[right] <= nums[n]){//舍去比right小的元素
left++;
}else{//比left大的元素全部符合条件
ret+=right-left;
right--;
}
}
}
return ret;
}
}
2.两数之和(难度:🟢1度)
OJ链接
- 题目描述
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]
- 算法原理
- 初始化left ， right 分别指向数组的左右两端（这⾥不是我们理解的指针，⽽是数组的下
标） - 当left < right 的时候，⼀直循环
- 当nums[left] + nums[right] == target 时，说明找到结果，记录结果，并且返回；
- 当nums[left] + nums[right] < target 时：
- 对于nums[left] ⽽⾔，此时nums[right] 相当于是nums[left] 能碰到的最⼤值（别忘了，这⾥是升序数组）。如果此时不符合要求，说明在这个数组⾥⾯，没有别的数符合nums[left] 的要求了（最⼤的数都满⾜不了你，你已经没救了）。因此，我们可以⼤胆舍去这个数，让left++ ，去⽐较下⼀组数据；
- 那对于nums[right] ⽽⾔，由于此时两数之和是⼩于⽬标值的， nums[right] 还可以选择⽐nums[left] ⼤的值继续努⼒达到⽬标值，因此right 指针我们按兵不动；
- 当nums[left] + nums[right] > target 时，同理我们可以舍去nums[right] （最⼩的数都满⾜不了你，你也没救了）。让right– ，继续⽐较下⼀组数据，⽽left 指针不变（因为他还是可以去匹配⽐nums[right] 更⼩的数的）。
- 初始化left ， right 分别指向数组的左右两端（这⾥不是我们理解的指针，⽽是数组的下
- 代码编写
class Solution {
public int[] twoSum(int[] price, int target) {
int left = 0;
int right = price.length-1;
while (left < right){
if (price[left]+price[right] == target){
return new int[]{price[left],price[right]};
}else if (price[left]+price[right] < target){
left++;
}else{
right--;
}
}
return new int[0];
}
}
3. 三数之和(难度:🟠4度)
OJ链接
- 题目描述
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。
示例 2：
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。
示例 3：
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。
- 算法原理
与两数之和稍微不同的是，题⽬中要求找到所有「不重复」的三元组。那我们可以利⽤在两数之和那⾥⽤的双指针思想，来对我们的暴⼒枚举做优化：- 先排序；
- 然后固定⼀个数a ：
- 在这个数后⾯的区间内，使⽤「双指针算法」快速找到两个数之和等于-a 即可。
但是要注意的是，这道题⾥⾯需要有==「去重」操作==~ - 找到⼀个结果之后， left 和right 指针要「跳过重复」的元素；
- 当使⽤完⼀次双指针算法之后，固定的a 也要「跳过重复」的元素。
最后一点要注意的是在去重操作移动指针的时候,不要出现越界情况.
还有一点小优化就是,在i遍历到>0的数据的时候,就可以停止了,这是因为在剩下的数字中再也找不得两个数字加起来等于负数了.
- 代码编写
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> ret = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0;i < nums.length;){
if (nums[i] > 0){//遇到大于0的,一定没有两个数使得条件成立
break;
}
int left = i + 1;
int right = nums.length-1;
while(left < right){
if (nums[left] + nums[right] == -nums[i]){
List<Integer> a = new ArrayList<>();
a.add(nums[i]);
a.add(nums[left]);
a.add(nums[right]);
ret.add(a);
left++;
right--;
while(left < nums.length && nums[left] == nums[left-1]){//left去重,且不可以越界
left++;
}
while(right > 0 && nums[right] == nums[right+1]){//right去重且不可以越界
right--;
}
}else if (nums[left] + nums[right] < -nums[i]){//与前面两数之和的原理相同
left++;
}else{
right--;
}
}
//i去重
i++;
while(i < nums.length && nums[i] == nums[i-1]){//不可以越界
i++;
}
}
return ret;
}
}
4.四数之和(难度:🔴5度)
- 题目描述
给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。
示例 1：
输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2：
输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]
- 算法原理
a. 依次固定⼀个数a ；
b. 在这个数a 的后⾯区间上，利⽤「三数之和」找到三个数，使这三个数的和等于target -a 即可。 - 代码编写
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> ret = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length;){
for (int j = i+1;j < nums.length;){
int left = j+1;
int right = nums.length-1;
long t = (long)target-nums[j]-nums[i];
while(left < right){
if (nums[left] + nums[right] == t){
List<Integer> a = new ArrayList<>();
a.add(nums[left]);
a.add(nums[right]);
a.add(nums[j]);
a.add(nums[i]);
ret.add(a);
left++;
right--;
while(left < nums.length && nums[left] == nums[left-1]){
left++;
}
while(right > 0 && nums[right] == nums[right+1]){
right--;
}
}else if(nums[left] + nums[right] < t){
left++;
}else{
right--;
}
}
j++;
while(j < nums.length && nums[j] == nums[j-1]){
j++;
}
}
i++;
while(i < nums.length && nums[i] == nums[i-1]){
i++;
}
}
return ret;
}
}
从今天的代码中,我们可以发现,这几道题目在不停的利用数组的单调性和双指针在优化暴力解法,排除掉暴力解法中的一些无效情况,以后在我们做题的时候,要充分利用单调性和双指针的配合.
