本站消息

站长简介/公众号


站长简介:逗比程序员,理工宅男,前每日优鲜python全栈开发工程师,利用周末时间开发出本站,欢迎关注我的微信公众号:幽默盒子,一个专注于搞笑,分享快乐的公众号

  价值13000svip视频教程,java大神匠心打造,零基础java开发工程师视频教程全套,基础+进阶+项目实战,包含课件和源码

  出租广告位,需要合作请联系站长


+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

2021-05(18)

2021-06(40)

2021-07(5)

LeetCode_剑指 Offer 57. 和为s的两个数字(利用set、双撞指针两种思路 Java实现)

发布于2021-06-14 09:38     阅读(69)     评论(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

  1. 创建 set 集合,用于保存数组元素;
  2. 遍历数组,判断集合中是否含有( target - nums [ i ] );
  3. 集合中若含有该数( target - nums [ i ] ),说明该数与当前遍历的数组元素之和为 target,则创建新数组保存并返回;
  4. 若不含有( 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黑洞网

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

26 0
收藏该文
已收藏

评论内容:(最多支持255个字符)