摘要:如果存在該差值,說明存在兩個數(shù)之和是目標(biāo)和。而哈希表方法中的則可以換成。如果要求的不是兩個數(shù)和和,而是找兩個數(shù)之差為特定值的配對呢同樣用哈希表可以解決。
Two Sum
</>復(fù)制代碼
Given an array of integers, find two numbers such that they add up to a specific target number.The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.
Input: numbers={2, 7, 11, 15}, target=9 Output: index1=1, index2=2
暴力法 Brute Force
復(fù)雜度
O(1)空間 O(n^2)時間
思路通過雙重循環(huán)遍歷數(shù)組中所有元素的兩兩組合,當(dāng)出現(xiàn)符合的和時返回兩個元素的下標(biāo)
注意內(nèi)層循環(huán)要從外層循環(huán)下標(biāo)加一開始,避免遍歷到兩個相同的元素
代碼</>復(fù)制代碼
public class Solution {
public int[] twoSum(int[] nums, int target) {
int[] result = new int[2];
if(nums.length < 2){
return result;
}
for(int i = 0 ; i < nums.length; i++){
for(int j = i + 1; j < nums.length; j++){
if((nums[i]+nums[j])==target){
result[0] = i + 1;
result[1] = j + 1;
return result;
}
}
}
return result;
}
}
哈希表 Hash Table
復(fù)雜度
O(n)空間 O(n)時間
思路第一次遍歷數(shù)組先將所有元素和它的下標(biāo)作為key-value對存入Hashmap中,第二次遍歷數(shù)組時根據(jù)目標(biāo)和與當(dāng)前元素之差,在Hashmap中找相應(yīng)的差值。如果存在該差值,說明存在兩個數(shù)之和是目標(biāo)和。此時記錄下當(dāng)前數(shù)組元素下標(biāo)并拿出Hashmap中數(shù)組元素下標(biāo)即可。Hashmap獲取元素的時間復(fù)雜度是O(1),所以總的時間復(fù)雜度仍不超過O(n)。
注意判定是否存在該差值時,要同時判斷該差值的下標(biāo)是不是當(dāng)前遍歷的元素下標(biāo),以避免重復(fù)
哈希表作為一個Collection,初始化時請注意聲明Key和Value的類型
代碼</>復(fù)制代碼
public class Solution {
public int[] twoSum(int[] nums, int target) {
Map map = new HashMap();
int[] res = new int[2];
for(int i = 0; i < nums.length; i++){
int diff = target - nums[i];
if(map.containsKey(nums[i])){
res[0] = map.get(nums[i]) + 1;
res[1] = i + 1;
}
map.put(diff, i);
}
return res;
}
}
2018/2 更新
</>復(fù)制代碼
class Solution:
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
numsMap = {}
for index in range(0, len(nums)):
num1 = nums[index]
num2 = target - num1
if num2 in numsMap:
return [index, numsMap[num2]]
else:
numsMap[num1] = index
2018/10
</>復(fù)制代碼
func twoSum(nums []int, target int) []int {
m := make(map[int]int)
result := make([]int, 2)
for i := 0; i < len(nums); i++ {
var curr = nums[i]
var diff = target - curr
result[0] = i
if _, ok := m[diff]; ok {
result[1] = m[diff]
return result
} else {
m[curr] = i
}
}
return result
}
排序雙指針法 Sorting with Two Pointers
復(fù)雜度
O(n)空間 O(nlogn)時間
思路首先將原數(shù)組復(fù)制一遍,對新數(shù)組進行排序。排序后將雙指針指向頭部與尾部元素,進行迭代。如果雙指針指向元素之和大于目標(biāo)和,則將尾部指針向前移一位,反之則將頭部指針向后移一位,直到雙指針指向元素之和等于目標(biāo)和,記錄這兩個元素的值,然后再遍歷一遍舊數(shù)組,找出這兩個元素的下標(biāo)。
注意該方法需要先將結(jié)果數(shù)組都初始化為-1,否則在遍歷舊數(shù)組時無法去除重復(fù),可能會將兩個下標(biāo)都存入同一個結(jié)果中
代碼</>復(fù)制代碼
private ArrayList> twoSum(int[] nums, int target){
int left = 0, right = nums.length - 1;
ArrayList> res = new ArrayList>();
while(left < right){
if(nums[left] + nums[right] == target){
ArrayList curr = new ArrayList();
curr.add(nums[left]);
curr.add(nums[right]);
res.add(curr);
do {
left++;
}while(left < nums.length && nums[left] == nums[left-1]);
do {
right--;
} while(right >= 0 && nums[right] == nums[right+1]);
} else if (nums[left] + nums[right] > target){
right--;
} else {
left++;
}
}
return res;
}
后續(xù) Follow Up
Q:如果不需要返回數(shù)組下標(biāo),只用返回兩個數(shù)本身呢?
A:如果只用返回兩個數(shù)本身,排序雙指針法可以做到O(1)空間,時間復(fù)雜度仍是O(nlogn)。而哈希表方法中的HashMap則可以換成HashSet。
Q:如果要求的不是兩個數(shù)和和,而是找兩個數(shù)之差為特定值的配對呢?
A:同樣用哈希表可以解決。如果要不用空間的話,也可以先排序,然后將兩個指針指向頭,兩個數(shù)差小于目標(biāo)時,將后指針向后移,否則將前指針向后移。
文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/64394.html
摘要:公眾號愛寫給定一個已按照升序排列的有序數(shù)組,找到兩個數(shù)使得它們相加之和等于目標(biāo)數(shù)。函數(shù)應(yīng)該返回這兩個下標(biāo)值和,其中必須小于。示例輸入輸出解釋與之和等于目標(biāo)數(shù)。 公眾號: 愛寫bug(ID:icodebugs) 給定一個已按照升序排列 的有序數(shù)組,找到兩個數(shù)使得它們相加之和等于目標(biāo)數(shù)。 函數(shù)應(yīng)該返回這兩個下標(biāo)值 index1 和 index2,其中 index1 必須小于 index2。...
摘要:公眾號愛寫給定一個已按照升序排列的有序數(shù)組,找到兩個數(shù)使得它們相加之和等于目標(biāo)數(shù)。函數(shù)應(yīng)該返回這兩個下標(biāo)值和,其中必須小于。示例輸入輸出解釋與之和等于目標(biāo)數(shù)。 公眾號: 愛寫bug(ID:icodebugs) 給定一個已按照升序排列 的有序數(shù)組,找到兩個數(shù)使得它們相加之和等于目標(biāo)數(shù)。 函數(shù)應(yīng)該返回這兩個下標(biāo)值 index1 和 index2,其中 index1 必須小于 index2。...
摘要:給出兩個非空的鏈表用來表示兩個非負(fù)的整數(shù)。如果,我們將這兩個數(shù)相加起來,則會返回一個新的鏈表來表示它們的和。需要考慮到兩個鏈表長度不同時遍歷方式鏈表遍歷完成時最后一位是否需要進一位。 ?給出兩個 非空 的鏈表用來表示兩個非負(fù)的整數(shù)。其中,它們各自的位數(shù)是按照 逆序 的方式存儲的,并且它們的每個節(jié)點只能存儲 一位 數(shù)字。如果,我們將這兩個數(shù)相加起來,則會返回一個新的鏈表來表示它們的和。 ...
摘要:給出兩個非空的鏈表用來表示兩個非負(fù)的整數(shù)。如果,我們將這兩個數(shù)相加起來,則會返回一個新的鏈表來表示它們的和。需要考慮到兩個鏈表長度不同時遍歷方式鏈表遍歷完成時最后一位是否需要進一位。 ?給出兩個 非空 的鏈表用來表示兩個非負(fù)的整數(shù)。其中,它們各自的位數(shù)是按照 逆序 的方式存儲的,并且它們的每個節(jié)點只能存儲 一位 數(shù)字。如果,我們將這兩個數(shù)相加起來,則會返回一個新的鏈表來表示它們的和。 ...
摘要:開坑,以后每周刷一兩道一題目兩數(shù)之和給定一個整數(shù)數(shù)組和一個目標(biāo)值,請你在該數(shù)組中找出和為目標(biāo)值的那兩個整數(shù),并返回他們的數(shù)組下標(biāo)。但是,你不能重復(fù)利用這個數(shù)組中同樣的元素。 開坑,以后每周刷一兩道LeetCode 一、題目 兩數(shù)之和: 給定一個整數(shù)數(shù)組 nums 和一個目標(biāo)值 target,請你在該數(shù)組中找出和為目標(biāo)值的那 兩個 整數(shù),并返回他們的數(shù)組下標(biāo)。你可以假設(shè)每種輸入只會對應(yīng)...
閱讀 2628·2021-11-18 10:02
閱讀 2286·2021-09-30 09:47
閱讀 1791·2021-09-27 14:01
閱讀 3116·2021-08-16 11:00
閱讀 3168·2019-08-30 11:06
閱讀 2399·2019-08-29 17:29
閱讀 1539·2019-08-29 13:19
閱讀 451·2019-08-26 13:54