Category | Difficulty | Likes | Dislikes |
---|---|---|---|
algorithms | Easy (47.92%) | 7893 | - |
我的答案
public int[] twoSum(int[] nums, int target) {
int i, j;
int[] res = new int[2];
for(i = 0; i < nums.length; i++){
for(j = i + 1; j < nums.length; j++){
if(nums[i] + nums[j] == target){
res[0] = i;
res[1] = j;
return res;
}
}
}
return res;
}
解题思路
遍历每个元素,并查找是否有一个元素与它相加等于 target
答案分析
时间复杂度 O(n2)
空间复杂度 O(1)
缺少异常处理
参考方案
public int[] twoSum(int[] nums, int target) {
Map<Integer,Integer> map = new HashMap<>();
for(int i = 0; i < nums.length; i++){
int tmp = target - nums[i];
if(map.containsKey(tmp)){
return new int[] {map.get(tmp),i};
}
map.put(nums[i], i);
}
throw new IllegalArgumentException("No Two Sum Solution");
}
时间复杂度 O(n)
空间复杂度 O(n)
备注
- HashMap 的 API
void clear()
Object clone()
boolean containsKey(Object key)
boolean containsValue(Object value)
Set<Entry<K, V>> entrySet()
V get(Object key)
boolean isEmpty()
Set<K> keySet()
V put(K key, V value)
void putAll(Map<? extends K, ? extends V> map)
V remove(Object key)
int size()
Collection<V> values()