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

相关文章

    无相关信息

最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台