Leetcode 題解 - 雙指針

leanxi 發(fā)布于2019-08-16 18:40 / 3153人閱讀

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

一、有序數(shù)組的 Two Sum

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

題目描述：在有序數(shù)組中找出兩個數(shù)，使它們的和為 target。

解題思路：使用雙指針，一個指針指向值較小的元素，一個指針指向值較大的元素。指向較小元素的指針從頭向尾遍歷，指向較大元素的指針從尾向頭遍歷。

如果兩個指針指向元素的和 sum == target，那么得到要求的結(jié)果；
如果 sum > target，移動較大的元素，使 sum 變小一些；
如果 sum < target，移動較小的元素，使 sum 變大一些。

import java.util.Arrays;

/**
 * Input: numbers={2, 7, 11, 15}, target=9
 * Output: index1=1, index2=2
 * 題目描述：在有序數(shù)組中找出兩個數(shù)，使它們的和為 target。
 *
 * 使用雙指針，一個指針指向值較小的元素，一個指針指向值較大的元素。指向較小元素的指針從頭向尾遍歷，
 * 指向較大元素的指針從尾向頭遍歷。
 *
 * 如果兩個指針指向元素的和 sum == target，那么得到要求的結(jié)果；
 * 如果 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)));
    }
}

二、兩數(shù)平方和

/**
     * 判斷一個數(shù)是否為2數(shù)平方和
     * 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;
    }