LeetCode_剑指 Offer 57. 和为s的两个数字（利用set、双撞指针两种思路 Java实现）
发布于2021-06-14 09:38 阅读(181) 评论(0) 点赞(26) 收藏(4)
题目描述：剑指 Offer 57. 和为s的两个数字
输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[2,7] 或者 [7,2]
示例 2：
输入：nums = [10,26,30,31,47,60], target = 40
输出：[10,30] 或者 [30,10]
思路描述：
思路1：
看到题目，总是首先想到暴力遍历，不出所料，超出时间限制;
思路2：利用set
- 创建 set 集合，用于保存数组元素;
- 遍历数组，判断集合中是否含有（ target - nums [ i ] ）;
- 集合中若含有该数（ target - nums [ i ] ）,说明该数与当前遍历的数组元素之和为 target，则创建新数组保存并返回；
- 若不含有（ target - nums [ i ] ）,则将当前正在遍历的元素添加至集合。
结果表明，应该还有最优解。
class Solution {
public int[] twoSum(int[] nums, int target) {
Set<Integer> set=new HashSet<Integer>();
for(int num:nums){
if(set.contains(target-num)){
return new int[]{num,target-num};
}else{
set.add(num);
}
}
return new int[0];
}
}
思路3：双指针（双撞指针）
定义两个指针 i 和 j ,其中 i 指向数组头部 nums [ 0 ] ，j 指向尾部 nums [ length - 1 ] ;
利用循环，
sum = nums [ i ] + nums [ j ] ;
若sum > target , j - - 指针左移；
若sum < target , j - - 指针左移；
若sum = target , 返回数组 [ nums [ i ] , nums [ j ] ]；
当 i > j 时跳出循环，说明未找到；
class Solution {
public int[] twoSum(int[] nums, int target) {
//方法2：双撞指针
int i=0,j=nums.length-1,sum=0;
while(i<j){
sum=nums[i]+nums[j];
if(sum>target){
j--;
}else if(sum<target){
i++;
}else{
return new int[] {nums[i],nums[j]};
}
}
return new int[0];
}
}
附上题目连接：
https://leetcode-cn.com/problems/he-wei-sde-liang-ge-shu-zi-lcof/
该题目还有进一步加大难度：剑指 Offer 57 - II. 和为s的连续正数序列
升级版题目解题思路链接：https://blog.csdn.net/weixin_51529267/article/details/117669445
所属网站分类: 技术文章 > 博客
作者：小泽圈儿郎
链接：http://www.javaheidong.com/blog/article/222618/5cec5768644fd2bd123e/
来源：java黑洞网
任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任
昵称:
评论内容：(最多支持255个字符)
---无人问津也好，技不如人也罢，你都要试着安静下来，去做自己该做的事，而不是让内心的烦躁、焦虑，坏掉你本来就不多的热情和定力