首页 > 代码库 > leetcode-1. Two Sum
leetcode-1. Two Sum
1. Two Sum
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].
很容易想到的一种解法,时间复杂度o(n*n):
public class Solution { public int[] twoSum(int[] nums, int target) { int[] a=new int[2]; for(int i=0;i<(nums.length-1);i++){ for(int j=i+1;j<nums.length;j++){ if((nums[i]+nums[j])==target){ a[0]=i; a[1]=j; return a; } } } return a; } }
下面是一种时间复杂度为o(n)的解法,使用了java中的HashMap:
public class Solution { public int[] twoSum(int[] nums, int target) { int[] a=new int[2]; Map<Integer,Integer> map=new HashMap<Integer,Integer>(); for(int i=0;i<nums.length;i++){ if(map.containsKey(target-nums[i])){ a[1]=i; a[0]=map.get(target-nums[i]); return a; } map.put(nums[i],i); } return a; } }
介绍一点HashMap的使用方法:
1,
Map的特性即「键-值」(Key-Value)匹配
java.util.HashMap实作了Map界面,
HashMap在内部实作使用哈希(Hash),很快的时间内可以寻得「键-值」匹配.
2,
Map<String, String> map =new HashMap<String, String>();
String key1 = "caterpillar";
String key2 = "justin";
map.put(key1, "caterpillar的讯息");
map.put(key2, "justin的讯息");
System.out.println(map.get(key1));
System.out.println(map.get(key2));
3,
可以使用values()方法返回一个实作Collection的对象,当中包括所有的「值」对象.
Map<String, String> map =new HashMap<String, String>();
map.put("justin", "justin的讯息");
map.put("momor", "momor的讯息");
map.put("caterpillar", "caterpillar的讯息");
Collection collection = map.values();
Iterator iterator = collection.iterator();
while(iterator.hasNext()) {
System.out.println(iterator.next());
}
System.out.println();
4,
Map<String, String> map =
new LinkedHashMap<String, String>();
map.put("justin", "justin的讯息");
map.put("momor", "momor的讯息");
map.put("caterpillar", "caterpillar的讯息");
for(String value : map.values()) {
System.out.println(value);
}
leetcode-1. Two Sum