- 求数值镜像问题可以考虑用hash
Two Sum
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1]
方法1：用哈希表，每遍历到一个元素num，看target-num是否在hash表中，如果在就得出答案，如果不在就将当前num放入哈希表中。复杂度 （存储开销大）
如果想得到所有的结果，可能需要vector<vector<int>>v;
方法2：如果给定的数组是已排序的数组，那么就可以设定lo和hi两个指针，如果这两个数字的和比target要大，那么就lo++，否则hi--，复杂度 （排序开销大）
Three Sum：
寻找3个数的和为0的组合：
从头开始每次取一个数作为sum，则此题变成了在后面的数组中寻找两个数其和为-sum，就和上面的过程一样。最终
Four Sum
- 思路一：先遍历第一个数，然后固定第一个数之后，转化为剩下元素的3SUM问题。
（我的思路是从后往前遍历，因为从后往前遍历的点值比较大，而且vector方便从后插入。去重采用的是unordered_map+string）
class Solution {
public:
static bool cmp(int &i, int &j){
return i<j;
}
vector<vector<int>> twosum(vector<int>nums,int target,int left,int right){
int i=left;
int j=right;
vector<vector<int>>res;
if(right-left<1){
return res;
}
while(i<j){
if(nums[i]+nums[j] >target ) {
j--;
} else if (nums[i]+nums[j] < target) {
i++;
}else{
vector<int>t;
t.push_back(nums[i]);
t.push_back(nums[j]);
res.push_back(t);
i++;
}
}
return res;
}
vector<vector<int>>threesum(vector<int>&nums,int target,int left,int right){
int i,j;
vector<vector<int>>v;
if(right-left<2){
return v;
}
for(i=right;i>=left+2;i--){
vector<vector<int>>vv;
vv=twosum(nums,target-nums[i],left,i-1);
for(j=0;j<vv.size();j++){
vv[j].push_back(nums[i]);
v.push_back(vv[j]);
}
}
return v;
}
vector<vector<int>> fourSum(vector<int>& nums, int target) {
sort(nums.begin(),nums.end(),cmp);
vector<vector<int>>res;
int size=nums.size();
int i,j,k;
if(size<4){
return res;
}
for(i=size-1;i>2;i--){
vector<vector<int>>v;
v=threesum(nums,target-nums[i],0,i-1);
for (j=0;j<v.size();j++){
v[j].push_back(nums[i]);
res.push_back(v[j]);
}
}
vector<vector<int>>Res;
unordered_map<string,bool>m;
for(i=0;i<res.size();i++){
string s="";
s=to_string(res[i][0])+","+to_string(res[i][1])+","+to_string(res[i][2])+","+to_string(res[i][3]);
if(m.count(s)){
}else{
m[s]=true;
Res.push_back(res[i]);
}
}
return Res;
}
};
不过理论上不去重也是可以的，在NSum里面用while(){i--};i--;跳过重复的末元素即可，但是似乎效率更低了/迷
class Solution {
public:
static bool cmp(int &i, int &j){
return i<j;
}
vector<vector<int>> twosum(vector<int>nums,int target,int left,int right){
int i=left;
int j=right;
vector<vector<int>>res;
if(right-left<1){
return res;
}
while(i<j){
if(nums[i]+nums[j] >target ) {
while (i < j && nums[j] == nums[j-1]){
j--;
}
j--;
} else if (nums[i]+nums[j] < target) {
while (i < j && nums[i] == nums[i+1]){
i++;
}
i++;
}else{
vector<int>t;
t.push_back(nums[i]);
t.push_back(nums[j]);
res.push_back(t);
while (i < j && nums[i] == nums[i+1]){
++i;
}
while(i<j && nums[j]==nums[j-1]){
--j;
}
i++;
}
}
return res;
}
vector<vector<int>>threesum(vector<int>&nums,int target,int left,int right){
int i,j;
vector<vector<int>>v;
if(right-left<2){
return v;
}
i=right;
while(i>=left+2){
vector<vector<int>>vv;
vv=twosum(nums,target-nums[i],left,i-1);
for(j=0;j<vv.size();j++){
vv[j].push_back(nums[i]);
v.push_back(vv[j]);
}
while(i>=left+2&&nums[i-1]==nums[i]){
i--;
}
i--;
}
return v;
}
vector<vector<int>> fourSum(vector<int>& nums, int target) {
sort(nums.begin(),nums.end());
vector<vector<int>>res;
int size=nums.size();
int i,j,k;
if(size<4){
return res;
}
i=size-1;
while(i>2){
vector<vector<int>>v;
v=threesum(nums,target-nums[i],0,i-1);
for (j=0;j<v.size();j++){
v[j].push_back(nums[i]);
res.push_back(v[j]);
}
while(i>2&&nums[i]== nums[i-1]){
i--;
}
i--;
}
return res;
}
};
- 思路二：先遍历两个数，求和，然后转化为剩下元素的2SUM问题。
/* 注意：调用这个函数之前一定要先给 nums 排序 */
vector<vector<int>> nSumTarget(
vector<int>& nums, int n, int start, int target) {
int sz = nums.size();
vector<vector<int>> res;
// 至少是 2Sum，且数组大小不应该小于 n
if (n < 2 || sz < n) return res;
// 2Sum 是 base case
if (n == 2) {
// 双指针那一套操作
int lo = start, hi = sz - 1;
while (lo < hi) {
int sum = nums[lo] + nums[hi];
int left = nums[lo], right = nums[hi];
if (sum < target) {
while (lo < hi && nums[lo] == left) lo++;
} else if (sum > target) {
while (lo < hi && nums[hi] == right) hi--;
} else {
res.push_back({left, right});
while (lo < hi && nums[lo] == left) lo++;
while (lo < hi && nums[hi] == right) hi--;
}
}
} else {
// n > 2 时，递归计算 (n-1)Sum 的结果
for (int i = start; i < sz; i++) {
vector<vector<int>>
sub = nSumTarget(nums, n - 1, i + 1, target - nums[i]);
for (vector<int>& arr : sub) {
// (n-1)Sum 加上 nums[i] 就是 nSum
arr.push_back(nums[i]);
res.push_back(arr);
}
while (i < sz - 1 && nums[i] == nums[i + 1]) i++;
}
}
return res;
}
多数组Sum
数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0
class Solution {
public:
int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D,int target) {
sort(A.begin(), A.end());
sort(B.begin(), B.end());
sort(C.begin(), C.end());
sort(D.begin(), D.end());
int i,counts=0;
for(i=0;i<A.size();i++){
counts+=threesumcount(B, C, D,target-A[i]);
}
return counts;
}
int threesumcount(vector<int>& A, vector<int>& B,vector<int>& C,int target){
int counts=0;
int i;
for(i = 0; i < A.size();i++){
counts+=twosumcount(C,B,target-A[i]);
}
return counts;
}
int twosumcount(vector<int>& A, vector<int>& B,int result){
int left =0;
int right=B.size();
int i,j;
int counts=0;
while(left<A.size() && right>-1){
if(A[left]+B[right]>result){
left++;
}else if(A[left]+B[right]<result){
right--;
}
else{
counts++;
left++;
}
}
return counts;
}
};
上面的代码本地没问题提交竟然报了错....下面是用hashmap的方法解的，无需排序更快。
class Solution {
public:
int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
unordered_map<int,int>m;
int i,j;
int result = 0;
for(i=0;i<A.size();i++){
for(j=0;j<B.size();j++){
if(m.count(A[i]+B[j])==0){
m[(A[i]+B[j])]=1;
}else{
m[(A[i]+B[j])]++;
}
}
}
int counts=0;
for(i=0;i<C.size();i++){
for(j=0;j<D.size();j++){
if(m.count(result-(C[i]+D[j]))){
counts+=m[result-(C[i]+D[j])];
}
}
}
return counts;
}
};
网友评论