167. 两数之和 II - 输入有序数组

LeetCode_167

题目描述

方法一：暴力法（使用哈希表）

class Solution {

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

        int len = numbers.length;

        HashMap<Integer, Integer> map = new HashMap<>();

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

            int next = target - numbers[i];

            if(map.containsKey(next)){

                return new int[]{map.get(next)+1, i+1};

            }

            map.put(numbers[i], i);

        }

        return new int[]{-1,-1};

    }

}

复杂度分析

时间复杂度：O(n)
空间复杂度：O(n)

方法二：双指针法

class Solution {

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

        int len = numbers.length;

        int low = 0, high = len-1;

        while(low <= high){

            int sum = numbers[low] + numbers[high];

            if(sum == target)

                return new int[]{low+1, high+1};

            if(sum < target)

                low++;

            else high--;

        }

        return new int[]{-1, -1};

    }

}

复杂度分析

时间复杂度：O(n)，其中 n 是数组的长度。两个指针移动的总次数最多为 n 次。
空间复杂度：O(1)。

巴特西

167. 两数之和 II - 输入有序数组 + 哈希表 + 双指针

167. 两数之和 II - 输入有序数组

LeetCode_167

题目描述

方法一：暴力法（使用哈希表）

复杂度分析

方法二：双指针法

复杂度分析

最新文章

热门文章