建站之星好吗,美容美发培训职业学校,北京壹零零壹网站建设,网站域名绑定好处验证回文数#xff08;验证回文数-CSDN博客#xff09;和判断在子序列#xff08;判断子序列-CSDN博客#xff09;已经在之前进行了计算#xff0c;今天有三个新的双指针问题#xff1a;
两数之和II—输入有序数组
给你一个下标从 1 开始的整数数组 numbers #xff0…验证回文数验证回文数-CSDN博客和判断在子序列判断子序列-CSDN博客已经在之前进行了计算今天有三个新的双指针问题
两数之和II—输入有序数组
给你一个下标从 1 开始的整数数组 numbers 该数组已按 非递减顺序排列 请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] 则 1 index1 index2 numbers.length 。
以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
你可以假设每个输入 只对应唯一的答案 而且你 不可以 重复使用相同的元素。
你所设计的解决方案必须只使用常量级的额外空间。
示例 1
输入numbers [2,7,11,15], target 9
输出[1,2]
解释2 与 7 之和等于目标数 9 。因此 index1 1, index2 2 。返回 [1, 2] 。
示例 2
输入numbers [2,3,4], target 6
输出[1,3]
解释2 与 4 之和等于目标数 6 。因此 index1 1, index2 3 。返回 [1, 3] 。
示例 3
输入numbers [-1,0], target -1
输出[1,2]
解释-1 与 0 之和等于目标数 -1 。因此 index1 1, index2 2 。返回 [1, 2]
思路
双指针的思想nums是一个有序的数组 因此我们可以使用这个特性即数据从小到大递增创建连个指针left指向0right指向数组末尾 若它们所指向的数据和为target直接返回 否则若值小于target,则left 否则 right--; public int[] twoSum(int[] numbers, int target) {int left0,rightnumbers.length-1;while(leftright){int sumnumbers[left]numbers[right];if(sumtarget)return new int []{left1,right1};else if(sumtarget)left;elseright--;}return new int[0];
}盛水最多的容器
给定一个长度为 n 的整数数组 height 。有 n 条垂线第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明你不能倾斜容器。
示例 1 输入[1,8,6,2,5,4,8,3,7]
输出49
解释图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下容器能够容纳水表示为蓝色部分的最大值为 49。
示例 2
输入height [1,1]
输出1
思路
最笨方法就是暴力解法就是经过两次循环计算出所有的储水量找出其中最大的并返回。但可能会超时
在这里我们可以使用双指针left指向0right指向height.length-1; 初始化res0表示当前的盛水量使用Math.min(height[left],height[right])*(right-left)来计算盛水量并与res进行比较将较大真存在res中然后移动left或right 若height[left]height[right],就left 否则right--(是因为每次都是有Math.min来计算所以移动较短的哪一方若移动较长的哪一方盛水量肯定减少直到leftright
public int maxArea(int[] height) {int left0,rightheight.length-1;int res0;while(left right){int kMath.min(height[left],height[right])*(right-left);if(kres)resk;if(height[left]height[right])left;elseright--;}return res;
}
三数之和
在看三数之和之前可以看看两数之和
两数之和
给定一个整数数组 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]
思路 第一种暴力解法 循环求解
public int[] twoSum(int[] nums, int target) {for(int i0;inums.length;i){for(int ji1;jnums.length;j){if(nums[i]nums[j]target)return new int []{i,j};}}return new int [0];
}
第二种哈希算法 创建一个hashmap存储数据和其对应的下标刚开始时hashmap为空循环遍历数组for(int i0;inums.length;i) 若hashmap中包含target-nums[i] 则返回其下标和i 否则就将其加入到hashmap中这里我刚开始不懂此时hashmap为空怎么去寻找数据为target是由两数在组成的,比如927,第一次访问2,map中找不到7,将2加入到map中,当访问7时就可以在map中找到2
public int[] twoSum(int[] nums, int target) {hashMapInteger mapnew HashMAp();for(int i0;inums.length;i){if(map.containsKey(target-nums[i]){return new int[]{map.get(target-nums[i],i};hashmap.put(nums[i],i);}return new int nums[0];
}
三数之和解题
给你一个整数数组 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 。
思路
1、将三数之和变成一个数固定的两数之和
2、如何保证元素不重复 首先需要对数组进行排序Ayyays.sort(nums),这样就变成不递减的数组 然后在进行遍历的过程中需要注意 此时遍历的数不能和它的前面一个数相同 最后可以借鉴有序数组的两数之和进行寻找
public ListListInteger threeSum(int[] nums) {ListListInteger listnew AyyayListListInteger();int first0;Arrays.sort(nums); // 进行排序for(first0;firstnums.length;first){//固定第一个数if(first0 nums[first]nums[first-1]) //此时遍历的数不能和它的前面一个数相同否则会出现重复return continue; int target0-nums[i]; //其余两数之和int thridnums.length-1; //第三个指针指向数组末尾for(int secondfirst1; secondnums.length;second){if(secondfirst1 nums[second]nums[second-1])continue;while(secondthrid nums[second]nums[thrid]target) //因为此时是从小到大排序的 所以当nums[second]nums[thrid]不大于target就有可能找到那个数了thrid--;if(secondthrid)break;if(nums[second]nums[thrid]){ListInteger resnew AyyayList();res.add(nums[first]);res.add(nums[second]);res.add(nums[thrid]);list.add(res);}}}return list;
}
