Leetcode 題解 - 雙指針

leanxi 發布于2019-08-16 18:40 / 3146人閱讀

摘要：一有序數組的題目描述在有序數組中找出兩個數，使它們的和為。解題思路使用雙指針，一個指針指向值較小的元素，一個指針指向值較大的元素。輸出二兩數平方和判斷一個數是否為數平方和開平方根

一、有序數組的 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題解

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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