Leetcode 1. Two Sum (java)

2018-03-02 08:31:37来历:cnblogs.com作者:CyanChan人点击

共享

解法一:

class Solution {    public int[] twoSum(int[] nums, int target) {        for (int i = 0; i < nums.length; i++) {            for (int j = i + 1; j < nums.length; j++) {                if( nums[i] + nums[j] == target ){                    int[] result = new int[2];                    result[0] = i;                    result[1] = j;                    return result;                }            }        }        return null;    }}

运用了两层循环进行遍历,时刻复杂度为O(n²)

解法二:

class Solution {    public int[] twoSum(int[] nums, int target) {        Hashtable<Integer,Integer> map = new Hashtable<Integer,Integer>();        for (int i = 0; i < nums.length; i++) {            map.put(nums[i],i);        }        for (int i = 0; i < nums.length; i++) {            int another = target - nums[i];       //过滤元素自身            if( map.get(another) != null &&map.get(another) > i ){                int[] result = new int[2];                result[0] = i;                result[1] = map.get(another);                return result;            }        }        return null;    }}

运用了哈希表进行查找,时刻复杂度为O(n)

解法一运用的是次序查找,时刻复杂度为O(n)

解法二运用的是哈希查找,时刻复杂度为O(1)

此外常用的查找:二分查找O(logn),二叉排序查找法O(logn),分块查找O(logn)

github地址:https://github.com/CyanChan/Leetcode-Record

相关文章

    无相关信息

微信扫一扫

明升m88.com微信大众渠道