兩數(shù)之和
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
這題給定一個數(shù)組， 返回 滿足 a + b = target 規(guī)則的 a,b 下標。
- 暴力的話
的時間內(nèi)check 這個規(guī)則就ok了。
- 如果這個數(shù)組是個排序數(shù)組， 那么可以使用雙指針 左右夾逼，因為數(shù)組有序， a+b 在 [a:b]區(qū)間內(nèi) ， a往右會導(dǎo)致 結(jié)果變大， b往左，會導(dǎo)致結(jié)果變小。這樣
的時間內(nèi)就可以找到 a+b = target 的情況。算上排序的時間復(fù)雜度，假設(shè)是快排 最終時間復(fù)雜度為
，空間復(fù)雜度為
- 我們借助哈希表 是否可以犧牲一點空間來獲得
當我們訪問a 點時， 我們把 target- a 也就是 b 點的值 存儲在哈希表中當作key, a點的下標當作value。那么如果b 點真的存在， 那么遍歷到b 點時，自然可以在哈希表中找到 之前存儲的a點下標。
#include <unordered_map>
using namespace std;
class Solution {
public:
// a+b = target --> b = target -a
// b : index(a)
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int,int> up;
vector<int> ans;
for(int a = 0; a< nums.size();a++){
if (up.find(nums[a]) != up.end()){
ans.push_back(up[nums[a]]);
ans.push_back(a);
return ans;
}
up[target-nums[a]] = a;
}
}
};
三數(shù)之和
Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:
The solution set must not contain duplicate triplets.
Example:
Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:
[ [-1, 0, 1],
[-1, -1, 2]]
這題的規(guī)則變成 a+b+c =target
- 暴力檢查這個規(guī)則 -->
- 如果我們固定住 c和 target ， 這題就可以轉(zhuǎn)化為 n 個 2sum 的問題，由上題我們知道 2sum 可以在 O(n) 的時間內(nèi)用哈希表解決， 那么最終就是
=
所以 我們這里固定住 C后 ，對a+b 使用雙指針 兩邊夾的辦法。
排序后， 我們很容易找到 a,b,c在排序數(shù)組上的關(guān)系, 如下圖
這題要考慮一個去重的問題，我這里處理的比較簡單。
if not ans or (ans and ans[-1] != temp):
ans.append(temp)
完整代碼
class Solution:
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
ans = []
nums = sorted(nums)
cur = 0
while cur < len(nums)-2:
if cur>0 and nums[cur] == nums[cur-1]:
cur+=1
continue
i = cur+1
j = len(nums) - 1
while i < j:
if nums[i]+ nums[j] == -nums[cur]:
temp = [nums[cur],nums[i],nums[j]]
if not ans or (ans and ans[-1] != temp):
ans.append(temp)
i+=1
j-=1
elif nums[i]+ nums[j] > -nums[cur]:
j-=1
else:
i+=1
cur+=1
return ans
3 sum closest
Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
Example:
Given array nums = [-1, 2, 1, -4], and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
現(xiàn)在 規(guī)則變成了 a+b+c+ gap = target ,輸出當gap 最小的時候，a,b,c的和。
實際上 這題和上一題并沒有什么區(qū)別， 仍然是 一樣的判斷條件，只是每次根據(jù)gap = target -a- b- c 更新最小的結(jié)果就ok了。
代碼如下：
class Solution:
def threeSumClosest(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
nums= sorted(nums)
_min = float("inf")
_distance = float("inf")
cur = 0
while cur < len(nums)-2:
i = cur+1
j = len(nums)-1
while i < j:
distance = abs(target - (nums[i] +nums[j] +nums[cur]))
if _distance > distance:
_distance = distance
_min = nums[i] +nums[j] +nums[cur]
if target > nums[i] +nums[j] + nums[cur]:
i+=1
elif target < nums[i] + nums[j] + nums[cur]:
j-=1
else:
return nums[i] + nums[j] + nums[cur]
cur+=1
return _min
四數(shù)之和
將 4 sum 轉(zhuǎn)化為 3 sum 在轉(zhuǎn)化為 2 sum
要注意 去重的問題。
#include <algorithm>
#include <vector>
using namespace std;
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
// res
vector<vector<int>> res;
if(nums.size() < 4){
return res;
}
// sort
sort(nums.begin(),nums.end());
int c= 0, d=0;
for(int a = 0; a < nums.size()-3; a++){
// 3 sum
if(a==0 || (a > 0 && nums[a] != nums[a-1]) ){
for(int b = a+1; b < nums.size()-2; b++){
//2 sum
if(b == a+1 || (b > a+1 && nums[b] != nums[b-1]) ){
c = b+1;
d = nums.size()-1;
while(c < d){
if (c> b+1 && nums[c] ==nums[c-1]){
c++;
continue;
}
if(d < nums.size()-1 && nums[d] == nums[d+1]){
d--;
continue;
}
if(nums[a] + nums[b] + nums[c]+ nums[d] > target){d--;}
else if(nums[a] + nums[b] + nums[c] + nums[d] < target){c++;}
else{
res.push_back(vector<int>{nums[a],nums[b],nums[c],nums[d]});
c++;d--;
}
}
}
}
}
}
return res;
}
};
