給定一個(gè)整數(shù)數(shù)組 nums 和一個(gè)目標(biāo)值 target，請(qǐng)你在該數(shù)組中找出和為目標(biāo)值的那兩個(gè)整數(shù)，并返回他們的數(shù)組下標(biāo)灌灾。
你可以假設(shè)每種輸入只會(huì)對(duì)應(yīng)一個(gè)答案。但是悲柱，數(shù)組中同一個(gè)元素不能使用兩遍锋喜。
示例:
給定 nums = [2, 7, 11, 15], target = 9
因?yàn)?nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
解法一
第一種最簡(jiǎn)單直接的想法即暴力解法，使用兩個(gè)循環(huán)逐個(gè)遍歷查找兩數(shù)之和是否等于 target 值。
public int[] twoSum(int[] nums, int target) {
for (int i = 0; i < nums.length-1; i++) {
for (int j = i+1; j < nums.length; j++) {
if (nums[i] + nums[j] == target) {
return new int[]{i,j};
}
}
}
return nums;
}
時(shí)間復(fù)雜度: O(n^2)
解法二
除此之外嘿般，應(yīng)該還可以有其他的思路段标。比如想辦法降低時(shí)間復(fù)雜度。能否少使用一次循環(huán)炉奴。使用 hashmap 的字典屬性逼庞，可以實(shí)現(xiàn)這一點(diǎn)，典型的 “空間換時(shí)間”瞻赶。
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; i++) {
int result = target - nums[i];
if (map.containsKey(result)) {
return new int[]{i, map.get(result)};
} else {
map.put(nums[i], i);
}
}
return new int[]{};
}
時(shí)間復(fù)雜度：O(n)
空間復(fù)雜度：O(n)
擴(kuò)展解法三(不可用赛糟，作參考)
另外一種思路，假如我們?cè)谔幚硪粋€(gè)排序數(shù)組砸逊。那么可是使用雙指針璧南，隊(duì)首隊(duì)尾各一個(gè)指針，逐個(gè)遞進(jìn)檢查隊(duì)首隊(duì)尾指針?biāo)赶虻脑刂褪σ荩欠衿ヅ渌疽小．?dāng)我用這個(gè)代碼測(cè)試的時(shí)候，發(fā)現(xiàn)沒通過的case卡在數(shù)組 [3,2,4] 上面篓像。說明題目給出的是無(wú)序數(shù)組动知。所以這個(gè)解法不可用。不過這也是一種題解思路遗淳，記錄在此拍柒。
/**
* 針對(duì)有序數(shù)組的雙指針法
* @param nums
* @param target
* @return
*/
public int[] twoSum(int[] nums, int target) {
Arrays.sort(nums);
int head = 0;
int tail = nums.length - 1;
int[] ans = new int[2];
for (int i = 0; i < nums.length; i++) {
int sum = nums[head] + nums[tail];
if (sum == target) {
ans[0] = head;
ans[1] = tail;
}
if (sum > target) {
tail--;
}
if (sum < target) {
head++;
}
}
return ans;
}
