數(shù)組系列
力扣數(shù)據(jù)結(jié)構(gòu)之?dāng)?shù)組-00-概覽
力扣.53 最大子數(shù)組和 maximum-subarray
力扣.128 最長(zhǎng)連續(xù)序列 longest-consecutive-sequence
力扣.167 兩數(shù)之和 II two-sum-ii
力扣.170 兩數(shù)之和 III two-sum-iii
力扣.653 兩數(shù)之和 IV two-sum-IV
力扣.016 最接近的三數(shù)之和 three-sum-closest
力扣.259 較小的三數(shù)之和 three-sum-smaller
題目
給你一個(gè)下標(biāo)從 1 開始的整數(shù)數(shù)組 numbers 洪规，該數(shù)組已按 非遞減順序排列笨使，請(qǐng)你從數(shù)組中找出滿足相加之和等于目標(biāo)數(shù) target 的兩個(gè)數(shù)。
如果設(shè)這兩個(gè)數(shù)分別是 numbers[index1] 和 numbers[index2] 澄者，則 1 <= index1 < index2 <= numbers.length 。
以長(zhǎng)度為 2 的整數(shù)數(shù)組 [index1, index2] 的形式返回這兩個(gè)整數(shù)的下標(biāo) index1 和 index2集嵌。
你可以假設(shè)每個(gè)輸入 只對(duì)應(yīng)唯一的答案 少欺，而且你 不可以 重復(fù)使用相同的元素正压。
你所設(shè)計(jì)的解決方案必須只使用常量級(jí)的額外空間。
示例 1：
輸入：numbers = [2,7,11,15], target = 9
輸出：[1,2]
解釋：2 與 7 之和等于目標(biāo)數(shù) 9 替饿。因此 index1 = 1, index2 = 2 语泽。返回 [1, 2] 。
示例 2：
輸入：numbers = [2,3,4], target = 6
輸出：[1,3]
解釋：2 與 4 之和等于目標(biāo)數(shù) 6 视卢。因此 index1 = 1, index2 = 3 踱卵。返回 [1, 3] 。
示例 3：
輸入：numbers = [-1,0], target = -1
輸出：[1,2]
解釋：-1 與 0 之和等于目標(biāo)數(shù) -1 据过。因此 index1 = 1, index2 = 2 惋砂。返回 [1, 2] 。
提示：
2 <= numbers.length <= 3 * 10^4
-1000 <= numbers[i] <= 1000
numbers 按 非遞減順序 排列
-1000 <= target <= 1000
僅存在一個(gè)有效答案
前言
這道題和 leetcode 的第一道題非常類似蝶俱，看起來非常簡(jiǎn)單班利。
不過今天回頭看饥漫，解法還是很多的榨呆。
大概可以有下面幾種：
暴力解法
數(shù)組排序+二分
HashSet/HashMap 優(yōu)化
v1-暴力解法
思路
直接兩次循環(huán)，找到符合結(jié)果的數(shù)據(jù)返回庸队。
這種最容易想到积蜻，一般工作中也是我們用到最多的。
實(shí)現(xiàn)
注意：這里的下標(biāo)從1開始彻消。一看就不是一個(gè)面向程序員的題目竿拆。
class Solution {
public int[] twoSum(int[] nums, int target) {
int[] res = new int[2];
final int n = nums.length;
for(int i = 0; i < n; i++) {
for(int j = i+1; j < n; j++) {
if(nums[i] + nums[j] == target) {
res[0] = i+1;
res[1] = j+1;
}
}
}
return res;
}
}
效果
超出時(shí)間限制 21 / 24 個(gè)通過的測(cè)試用例
小結(jié)
暴力算法雖然容易想到，不過如果遇到特別長(zhǎng)的場(chǎng)景用例宾尚，會(huì)直接超時(shí)丙笋。
我們?nèi)绾胃倪M(jìn)一下呢？
排序是這個(gè)場(chǎng)景另一種很有用的方式煌贴。
v2-排序+二分
思路
我們希望排序御板，然后通過二分法來提升性能。
這里就發(fā)現(xiàn)牛郑，題目已經(jīng)幫我排序好了怠肋。所以第一題的麻煩的部分全部省略了。
代碼
class Solution {
public int[] twoSum(int[] nums, int target) {
final int n = nums.length;
for(int i = 0; i < n; i++) {
int other = target - nums[i];
int j = binarySearch(nums, other, i+1);
if(j >= 0) {
return new int[]{i+1, j+1};
}
}
return new int[]{-1, -1};
}
private int binarySearch(int[] nums,
int target,
int startIx) {
int left = startIx;
int right = nums.length-1;
while (left <= right) {
int mid = left + (right - left) / 2;
int val = nums[mid];
if(val == target) {
return mid;
}
if(val > target) {
right = mid-1;
} else {
left = mid+1;
}
}
return -1;
}
}
效果
4ms 16.87%
嗯淹朋？
這個(gè)竟然不是本題目的最佳解法嗎笙各？
v3-HashMap
思路
在我們寫完上面的寫法之后，有沒有一種感覺础芍？
既然是要找另一部分的值杈抢，那么直接 Hash，復(fù)雜度 O(1) 不是更快仑性？
是的春感，你真是個(gè)小機(jī)靈鬼。
哈希在這種等于的場(chǎng)景是最快的，不過上面的二分適用性更廣一些鲫懒，比如查詢大于或者小于的時(shí)候嫩实。
當(dāng)然本體限制了，必須常量的空間窥岩，所以這種解法被限制了甲献，不過也值得看一下。
我們先來看一下哈希的解法颂翼。
代碼
注意：這里的順序要求有序晃洒，所以返回的時(shí)候和 T1 要反過來。
class Solution {
public int[] twoSum(int[] nums, int target) {
int n = nums.length;
HashMap<Integer, Integer> hashMap = new HashMap<>();
for(int i = 0; i < n; i++) {
int other = target - nums[i];
if(hashMap.containsKey(other)) {
int j = hashMap.get(other);
return new int[]{j+1, i+1};
}
// 存儲(chǔ)
hashMap.put(nums[i], i);
}
return new int[]{-1, -1};
}
}
效果
7ms 6.01%
只能說性能很差朦乏，猜測(cè)是 map 構(gòu)建導(dǎo)致的耗時(shí)球及，不然這個(gè)作為 O(n) 的解法一定性能更好才對(duì)。
說明這一題一定有更加適合的解法呻疹。
v4-雙指針
思路
其實(shí)在 v2 二分法的排序思路上吃引，我們可以受到一些啟發(fā)。
排序+二分是我們非常老實(shí)的一次遍歷刽锤，然后再二分查找镊尺，復(fù)雜度為 n*log(n)
那么有沒有可能在有序的數(shù)組中不用這么麻煩？
那就要說到巧妙的雙指針了并思。
雙指針
我們定義兩個(gè)指針
left=0
right=n-1
sum=num[left]+num[right-1]
因?yàn)閿?shù)組有有序的庐氮，所以只有 3 種情況：
sum == target 直接滿足
sum < target，left++
sum > target, right--
代碼
class Solution {
public int[] twoSum(int[] nums, int target) {
int n = nums.length;
int left = 0;
int right = n-1;
while (left < right) {
int sum = nums[left] + nums[right];
if(sum == target) {
return new int[]{left+1, right+1};
}
if(sum < target) {
left++;
}
if(sum > target) {
right--;
}
}
return new int[]{-1, -1};
}
}
效果
1ms
99.36%
小結(jié)
這類題目的思路基本都是類似的宋彼。
我們有常見的幾種解法：
- 暴力
2）借助 Hash
- 排序+二分
4）雙指針==》針對(duì)有序數(shù)組
我們后續(xù)將看一下 n 數(shù)之和的系列弄砍，感興趣的小伙伴點(diǎn)點(diǎn)贊，關(guān)注不迷路输涕。
