兩數(shù)之和
題目要求
給定一個(gè)整數(shù)數(shù)組和一個(gè)目標(biāo)值,找出數(shù)組中和為目標(biāo)值的兩個(gè)數(shù).
你可以假設(shè)每個(gè)輸入只對應(yīng)一種答案,且同樣的元素不能被重復(fù)利用.
示例:
給定 nums = [2, 7, 11, 15], target = 9
因?yàn)?nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
思路
三種辦法:
- 第一種辦法耗時(shí)72ms
- 第二種辦法耗時(shí)12ms
- 第三種辦法耗時(shí)9ms
代碼
暴力法:兩個(gè)循環(huán)
時(shí)間復(fù)雜度:O(n2)
空間復(fù)雜度:O(1)
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[j] == target - nums[i]) {
return new int[] { i, j };
}
}
}
throw new IllegalArgumentException("No two sum solution");
}
暴力法的遍體,可以加快一點(diǎn)效率,但是本質(zhì)沒有改變
public int[] twoSum(int[] nums, int target) {
int[] result = new int[2];
if(nums == null || nums.length < 2){
return result;
}
for(int i = 0;i < nums.length;i++){
//尾指針的重置
int j = nums.length-1;
//判斷i
while(i < j){
if(nums[i] + nums[j] == target){
result[0] = i;
result[1] = j;
return result;
}else{
j--;
}
}
}
return result;
}
兩遍哈希表
為了降低查找時(shí)間,我們可以通過使用hash表的方式來以空間換時(shí)間,第一次將全部數(shù)據(jù)存入hash表,然后第二次通過target-nums[i]的方式來查找是否存在,因?yàn)榈诙蔚牟檎視r(shí)間復(fù)雜度近似為O(1).
時(shí)間復(fù)雜度:O(n)
空間復(fù)雜度:O(n)
public int[] twoSum(int[] nums, int target) {
if(nums == null || nums.length < 2){
return null;
}
//兩遍hash表
HashMap<Integer,Integer> hash = new HashMap<>();
for(int i = 0; i < nums.length;i++){
hash.put(nums[i],i);
}
for(int i = 0;i < nums.length;i++){
Integer result = hash.get(target - nums[i]);
if(result != null && result != i){
return new int[]{i,result};
}
}
return null;
}
一遍哈希表
上述過程也可以在一遍之內(nèi)完成,邊存邊判斷.但是對時(shí)間復(fù)雜度和空間復(fù)雜度沒有太大的影響
時(shí)間復(fù)雜度:O(n)
空間復(fù)雜度:O(n)
public int[] twoSum(int[] nums, int target) {
if(nums == null || nums.length < 2){
return null;
}
//一遍hash表
HashMap<Integer,Integer> hash = new HashMap<>();
for(int i = 0; i < nums.length;i++){
int num = target - nums[i];
if(hash.containsKey(num)){
return new int[]{i,hash.get(num)};
}
hash.put(nums[i],i);
}
return null;
}
