Leetcode 题解 - 双指针

leanxi 发布于2019-08-16 18:40 / 3076人阅读

摘要：一有序数组的题目描述在有序数组中找出两个数，使它们的和为。解题思路使用双指针，一个指针指向值较小的元素，一个指针指向值较大的元素。输出二两数平方和判断一个数是否为数平方和开平方根

一、有序数组的 Two Sum

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

题目描述：在有序数组中找出两个数，使它们的和为 target。

解题思路：使用双指针，一个指针指向值较小的元素，一个指针指向值较大的元素。指向较小元素的指针从头向尾遍历，指向较大元素的指针从尾向头遍历。

如果两个指针指向元素的和 sum == target，那么得到要求的结果；
如果 sum > target，移动较大的元素，使 sum 变小一些；
如果 sum < target，移动较小的元素，使 sum 变大一些。

import java.util.Arrays;

/**
 * Input: numbers={2, 7, 11, 15}, target=9
 * Output: index1=1, index2=2
 * 题目描述：在有序数组中找出两个数，使它们的和为 target。
 *
 * 使用双指针，一个指针指向值较小的元素，一个指针指向值较大的元素。指向较小元素的指针从头向尾遍历，
 * 指向较大元素的指针从尾向头遍历。
 *
 * 如果两个指针指向元素的和 sum == target，那么得到要求的结果；
 * 如果 sum > target，移动较大的元素，使 sum 变小一些；
 * 如果 sum < target，移动较小的元素，使 sum 变大一些。
 */
public class TwoSum {
    public static int[] towSum(int[] numbers, int target){
        int i = 0;
        int j = numbers.length - 1;
        int sum;
        while(i < j){
            sum = numbers[i] + numbers[j];
            if(sum > target){
                j--;
            }else if(sum < target){
                i++;
            }else{
                return new int[]{i+1,j+1};
            }
        }
        return null;
    }

    public static void main(String[] args) {
        int numbers[] = {2,7,11,15};
        int target = 9;
        //输出[1, 2]
        System.out.println(Arrays.toString(TwoSum.towSum(numbers, target)));
    }
}

二、两数平方和

/**
     * 判断一个数是否为2数平方和
     * Input: 5
     * Output: True
     * Explanation: 1 * 1 + 2 * 2 = 5
     * @param number
     * @return
     */
    public static boolean judgeSqrtSum(int number){
        int i = 0;
        //开平方根
        int j = (int)Math.sqrt(number);
        int result;
        while(i < j){
            result = i * i + j * j;
            if(result < number){
                i ++;
            }else if(result > number){
                j--;
            }else{
                return true;
            }
        }
        return false;
    }

云服务器 GPU云服务器双指针 js 双指针仪表盘题解 oj题解

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/75543.html

LeetCode 283. 移动零【c++/java详细题解】

摘要：尽量减少操作次数。样例如样例所示，数组，移动完成后变成，下面来讲解双指针的做法。这样我们就完成了元素的移动，同时也保持了非元素的相对顺序。目录 1、题目2、思路...

cnsworder 2021-09-03 10:29 评论0 收藏0
思维导图整理大厂面试高频数组补充1: 最接近的三数之和和三数之和的两个不同之处, 力扣16

摘要：此专栏文章是对力扣上算法题目各种方法的总结和归纳整理出最重要的思路和知识重点并以思维导图形式呈现当然也会加上我对导图的详解目的是为了更方便快捷的记忆和回忆算法重点不用每次都重复看题解毕竟算法不是做了一遍就能完全记住的所 ...

longmon 2021-11-12 10:36 评论0 收藏0
LeetCode 攻略 - 2019 年 7 月上半月汇总（55 题攻略）

摘要：微信公众号记录截图记录截图目前关于这块算法与数据结构的安排前。已攻略返回目录目前已攻略篇文章。会根据题解以及留言内容，进行补充，并添加上提供题解的小伙伴的昵称和地址。本许可协议授权之外的使用权限可以从处获得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一目录不...

warmcheng 2019-08-26 10:09 评论0 收藏0
❤️思维导图整理大厂面试高频数组9: 删除重复元素的通解问题, 力扣26/80❤️

此专栏文章是对力扣上算法题目各种方法的总结和归纳, 整理出最重要的思路和知识重点并以思维导图形式呈现, 当然也会加上我对导图的详解. 目的是为了更方便快捷的记忆和回忆算法重点(不用每次都重复看题解), 毕竟算法不是做了一遍就能完全记住的. 所以本文适合已经知道解题思路和方法, 想进一步加强理解和记忆的朋友, 并不适合第一次接触此题的朋友(可以根据题号先去力扣看看官方题解, 然后再看本文内容). 关...

MasonEast 2021-09-04 16:40 评论0 收藏0
思维导图整理大厂面试高频数组24: 合并两个有序数组的两种双指针思想, 力扣88

摘要：此专栏文章是对力扣上算法题目各种方法的总结和归纳整理出最重要的思路和知识重点并以思维导图形式呈现当然也会加上我对导图的详解目的是为了更方便快捷的记忆和回忆算法重点不用每次都重复看题解毕竟算法不是做了一遍就能完全记住的所 ...

darkerXi 2021-11-17 09:33 评论0 收藏0