Leetcode 1. Two Sum (java)

2018-03-02 by 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

最新更新:

第七城市

栏目导航(关闭)