营口沿海开发建设有限公司网站,PHP网站开发有哪些框架,网站与新闻建设总结,app开发企业一般选择目录 两数之和
题目链接
题目描述
思路分析
代码实现
三数之和
题目链接
题目描述
思路分析
代码实现
四数之和
题目链接
题目描述
思路分析
代码实现 两数之和
题目链接
LCR 179. 查找总价格为目标值的两个商品 - 力扣#xff08;LeetCode#xff09;
题目…目录 两数之和
题目链接
题目描述
思路分析
代码实现
三数之和
题目链接
题目描述
思路分析
代码实现
四数之和
题目链接
题目描述
思路分析
代码实现 两数之和
题目链接
LCR 179. 查找总价格为目标值的两个商品 - 力扣LeetCode
题目描述
购物车内的商品价格按照升序记录于数组 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]
思路分析
题目要求我们找到两个价格之和刚好为 target 的商品且只需要返回任意一组结果
我们可以使用暴力枚举的方式列出所有的两个数字的组合判断这两个数字的和是否等于目标值
但是此时的时间复杂度为 O(N^2)且会超时
由于数组是升序的因此我们可以使用 对撞指针 来解决这个问题
我们定义两个指针分别指向数组的最左端和最右端 若 nums[left] nums[right] target此时 nums[right] 为最大值不能再增加了因此我们需要让 nums[left] 变大因此 left让 nums[left] 增加 若 nums[left] nums[right] target此时 nums[left] 为最小值不能再减小了因此我们让 right--减小 nums[right] 的值从而让两数之和减小 若 nums[left] nums[right] target说明找到结果了记录结果并返回即可
接下来我们就来尝试编写代码
代码实现
class Solution {public int[] twoSum(int[] price, int target) {int len price.length;int left 0, right len - 1;while(left right) {if (price[left] price[right] target) {left;} else if(price[left] price[right] target) {right--;} else {return new int[] {price[left], price[right]};}}return new int[2];}
}
三数之和
题目链接
15. 三数之和 - 力扣LeetCode
题目描述
给你一个整数数组 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 。
思路分析
题目要求我们找到 所有和为 0 且不重复的三元组相比于上述的两数之和此时我们要找到所有和为0的三元组且不能重复
我们同样可以利用 对撞指针 的思想来解决这个问题
由于数组不是有序的因此我们先对其进行排序
接着由于要找三个数因此我们可以先固定一个数 nums[k]此时就需要找到两个数它们的和 target 为 -nums[k] 若 nums[left] nums[right] targetleft
若 nums[left] nums[right] targetright--
若 nums[left] nums[right] target找到一组和为 0 的三元组但是在 [left 1, right - 1] 区间内可能还存在和为 target 的二元组因此 leftright--
但是由于不能出现重复的三元组因此我们需要对其进行 去重 操作 当找到一个结果时left 和 right 都需要跳过重复的元素
此外当结束完一次循环后固定的 k 也需要进行去重操作 在分析完解题思路之后我们就来尝试编写代码解决问题
代码实现
class Solution {public ListListInteger threeSum(int[] nums) {int len nums.length;ListListInteger ret new ArrayList();// 对元素进行排序Arrays.sort(nums);for(int i 0; i len - 2; ) {int target 0 - nums[i];int left i 1;int right len - 1;while(left right) {int sum nums[left] nums[right];if(sum target) {right--;} else if(sum target) {left;} else {ret.add(new ArrayListInteger(Arrays.asList(nums[i], nums[left], nums[right])));// 继续找left;right--;// 去重while(left right nums[left] nums[left - 1]) {left;}while(left right nums[right] right 1) {right--;}}}// 去重i;while(i len nums[i] nums[i - 1]) {i;}}return ret;}
}
四数之和
题目链接
18. 四数之和 - 力扣LeetCode
题目描述
给你一个由 n 个整数组成的数组 nums 和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] 若两个四元组元素一一对应则认为两个四元组重复
0 a, b, c, d na、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]]
思路分析
在解决了三数之和问题之和四数之和就变得非常简单我们只需要 1对数组进行排序 2固定a 位置的数 3在数a的前面区间上利用三数之和找到三个数使得这三个数的和等于 target - nums[a] 即可 代码实现
class Solution {public ListListInteger fourSum(int[] nums, int target) {ListListInteger ret new ArrayList(); int len nums.length;if(len 4) {return ret;}// 排序Arrays.sort(nums);int i 0;while(i len - 3) {int j i 1;while(j len - 2) {int left j 1;int right len - 1;long t (long)target - nums[i] - nums[j];while(left right) {if(nums[left] nums[right] t) {left;} else if(nums[left] nums[right] t){right--;} else {ret.add(new ArrayListInteger(Arrays.asList(nums[i], nums[j], nums[left], nums[right])));// 去除左边重复元素left;while(left right nums[left] nums[left - 1]) {left;}// 去除右边重复元素right--;while(left right nums[right] nums[right1]) {right--;}}}j;while(j len - 2 nums[j] nums[j - 1]) {j;}}i;while(i len - 3 nums[i] nums[i - 1]) {i;}}return ret;}
}
