剑指 Offer 57. 和为s的两个数字

Offer_57

题目详情

使用二分法

package com.walegarrett.offer;

/**

 * @Author WaleGarrett

 * @Date 2021/2/10 18:57

 */

/**

 * 题目详情：输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。

 *          如果有多对数字的和等于s，则输出任意一对即可。

 */

import java.util.ArrayList;

import java.util.Arrays;

/**

 * 解法一：使用二分法查找法

 */

public class Offer_57 {

    public int[] twoSum(int[] nums, int target) {

        int len = nums.length;

        boolean flag = false;

        int[] result = new int[2];

        int i,index=0;

        for(i=0; i<len; i++){

            int now = nums[i];

            int another = target-now;

            int left = i+1,right = len;

            if(left == len)

                break;

            index = Arrays.binarySearch(nums, left, right, another);

            if(index >= 0){

                flag = true;

                break;

            }

        }

        if(flag)

            return new int[]{nums[i],nums[index]};

        return new int[0];

    }

}

使用双指针法

/**

 * 解法二：使用双指针法

 */

class Offer_57_1 {

    public int[] twoSum(int[] nums, int target) {

        int len = nums.length;

        int i = 0, j=len-1;

        while(i<j){

            int sum = nums[i] + nums[j];

            if(sum < target)

                i++;

            else if(sum > target)

                j--;

            else return new int[]{nums[i], nums[j]};

        }

        return new int[0];

    }

}

复杂度分析

时间复杂度 O(N) ： N 为数组 nums 的长度；双指针共同线性遍历整个数组。
空间复杂度 O(1) ：变量 i, j 使用常数大小的额外空间。

巴特西

剑指 Offer 57. 和为s的两个数字 + 二分法 + 双指针

剑指 Offer 57. 和为s的两个数字

Offer_57

题目详情

使用二分法

使用双指针法

复杂度分析

最新文章

热门文章