▶ 问题：给定一个数组 nums 及一个目标值 target，求数组中是否存在 n 项的和恰好等于目标值
▶ 第 1题，n = 2，要求返回解
● 代码，160 ms，穷举法，时间复杂度 O(n2)，空间复杂度 O(1)
class Solution
{
public:
vector<int> twoSum(vector<int> nums, int target)
{
int i, j;
for (i = ; i < nums.size()-; i++)
{
for (j = i + ; j < nums.size(); j++)
{
if (nums[i] + nums[j] == target)
return vector<int> {i, j};
}
}
return vector<int>{};
}
};
● 代码，9 ms，排序后夹逼，需要构造一个结构来保存下标，连着下标一起排序。时间复杂度 O(n log n)，空间复杂度 O(1)
class Solution
{
public:
struct Node
{
int val;
int index;
Node(int pval, int pindex) : val(pval), index(pindex) {}
bool operator < (const Node& b) const {return val < b.val;}
}; vector<int> twoSum(vector<int>& nums, int target)
{
int i, j, temp;
vector<Node> nums2;
for (i = ; i < nums.size(); i++)
nums2.push_back(Node(nums[i], i));
sort(nums2.begin(), nums2.end());
for (i = , j = nums2.size() - ; i < j; (temp > target) ? j-- : i++ )
{
if ((temp = nums2[i].val + nums2[j].val) == target)
return vector<int>{nums2[i].index, nums2[j].index};
}
return vector<int>{};
}
};
● 代码，10 ms，使用散列表，遍历数组时将项放入散列表，同时检查当前项和散列表中已经有的项是否构成问题的解，利用散列表查找时间为常数的特点加快检查速度，最快的解法算法与之相同。时间复杂度 O(n)，空间复杂度 O(n)
class Solution
{
public:
vector<int> twoSum(vector<int> nums, int target)
{
int i;
unordered_map<int, int> map;
for (i = ; i < nums.size(); i++)
{
if (map.find(target - nums[i])!=map.end())
return vector<int>{map[target - nums[i]], i };
map[nums[i]] = i;
}
return vector<int>{};
}
};
▶ 第 15 题，n = 3，target = 0
● 大佬的代码，110 ms，排序后夹逼，先指定第一个（最小的）元素，剩下的两个元素使用前面二元和的方法进行夹逼，并跳掉一些多余分支，最快的解法算法与之相同，时间复杂度 O(n2)，空间复杂度 O(1)
class Solution
{
public:
vector<vector<int> > threeSum(vector<int> &num)
{
int i, left, right;
vector<vector<int>> output; sort(num.begin(), num.end());
for (i = ; i < num.size();)
{
if (num[i] > ) // 第一个元素已经大于零，则三个元素的和不可能等于零，剩下的界都不用检查了
break;
for (left = i + , right = num.size() - ; left < right;) // 搜索二元和,可能有多解，必须全部搜索完
{
if (num[left] + num[right] + num[i] < )
left++;
else if (num[left] + num[right] + num[i] > )
right--;
else
{
output.push_back(vector<int>{num[i], num[left], num[right]});
for (left++; left < right && num[left] == num[left - ]; left++); // 跳过第二个数重复的情况
for (right--; left < right && num[right] == num[right + ]; right--); // 跳过第三个数重复分情况
}
}
for (i++; i < num.size() && num[i] == num[i - ]; i++); // 跳过第一个数重复分情况，即调整下一次检查的起点
}
return output;
}
};
▶ 第 16 题，n = 3，求最近似解，第 259 题要收费 Orz
● 代码，6 ms，排序后夹逼，使用 output 来记录当前最优解的信息。最快的解法算法与之相同，时间复杂度 O(n2)，空间复杂度 O(1)
class Solution
{
public:
inline int diff(int a, int b) { return (a > b) ? (a - b) : (b - a); } int threeSumClosest(vector<int> &num, int target)
{
int i, target2, left, right, sum2, output; std::sort(num.begin(), num.end());
for (i = , output = INT_MAX>>; i < num.size();)
{
for (target2 = target - num[i], left = i + , right = num.size() - ; left < right;)
{
sum2 = num[left] + num[right];
if (sum2 < target2)
left++;
else if (sum2 > target2)
right--;
else
return target;
if (diff(sum2, target2) < diff(target,output))
output = sum2 + num[i];
}
for (i++; i < num.size() && num[i] == num[i - ]; i++);
}
return output;
}
};
▶ 第18 题，n = 4
● 代码，12 ms，排序后夹逼，先指定两个较小的元素，剩下的两个元素使用前面二元和的方法进行夹逼，并跳掉一些多余分支，最快的解法算法与之相同，时间复杂度 O(n3)，空间复杂度 O(1)
class Solution4
{
public:
vector<vector<int>> fourSum(vector<int>& nums, int target)
{
int n, i, j, left, right, sum;
vector<vector<int>> output;
n = nums.size();
sort(nums.begin(), nums.end());
for (i = ; i < n - ; i++) // 指定第一个元素
{
if (i > && nums[i] == nums[i - ] || nums[i] + nums[n - ] + nums[n - ] + nums[n - ] < target)
continue; // 跳过第一个元素重复或过小的情况
if (nums[i] + nums[i + ] + nums[i + ] + nums[i + ] > target)
break; // 第一个元素过大，结束搜索
for (j = i + ; j < n - ; j++) // 指定第二个元素
{
if (j > i + && nums[j] == nums[j - ] || nums[i] + nums[j] + nums[n - ] + nums[n - ] < target)
continue; // 跳过第二个元素重复过小的情况
if (nums[i] + nums[j] + nums[j + ] + nums[j + ]>target)
break; // 第二个元素过大，结束搜索
for(left = j + , right = n - ; left < right;) // 搜索第三和第四个元素
{
sum = nums[left] + nums[right] + nums[i] + nums[j];
if (sum < target)
left++;
else if (sum > target)
right--;
else
{
output.push_back(vector<int>{nums[i], nums[j], nums[left], nums[right]});
for (left++; nums[left] == nums[left - ] && left < right; left++);
for (right--; nums[right] == nums[right + ] && left < right; right--);
}
}
}
}
return output;
}
};
▶ 第 167 题，n = 2，默认已经排好了序，可以使用第 1 题结果，第170 题要付费 Orz
● 夹逼，7 ms，时间复杂度 O(n)
class Solution
{
public:
vector<int> twoSum(vector<int>& numbers, int target)
{
int left, right;
vector<int>output;
for (left = , right = numbers.size() - ; left < right;)
{
if (numbers[left] + numbers[right] == target)
return vector<int>{left + , right + };
else if (numbers[left] + numbers[right] > target)
right--;
else
left++;
}
return vector<int>();
}
};
● 大佬的代码，7 ms，使用二分法加速，时间复杂度 O(log n)
class Solution
{
public:
int largestSmallerOrLastEqual(vector<int>& numbers, int start, int end, int target)
{
int lp, rp, mp;
for (lp = start, rp = end, mp = lp + (rp - lp) / ; lp <= rp; mp = lp + (rp - lp) / )
{
if (numbers[mp] > target)
rp = mp - ;
else
lp = mp + ;
}
return rp;
}
int smallestLargerOrFirstEqual(vector<int>& numbers, int start, int end, int target)
{
int lp, rp, mp;
for (lp = start, rp = end, mp = lp + (rp - lp) / ; lp <= rp; mp = lp + (rp - lp) / )
{
if (numbers[mp] < target)
lp = mp + ;
else
rp = mp - ;
}
return lp;
}
vector<int> twoSum(vector<int>& numbers, int target)
{
const int n = numbers.size();
if (numbers.size() == )
return vector<int>{};
int start, end;
for (start = , end = n - ; start < end;)
{
if (numbers[start] + numbers[end] == target)
return vector<int> {start + , end + };
if (numbers[start] + numbers[end] > target)
end = largestSmallerOrLastEqual(numbers, start, end, target - numbers[start]);// end 向前移动到满足 numbers[end] <= target - numbers[start] 的最后一个整数
else
start = smallestLargerOrFirstEqual(numbers, start, end, target - numbers[end]);// start 向后移动到满足 numbers[start] >= target - numbers[end] 的第一个整数
}
return vector<int>{};
}
};
▶ 第 454 题，n = 4，每个加数分别从指定的集合中选出
● 自己的方法，1550 ms，这是将第 18 题的算法移植过来得到的，在使用计数器 counta，countb，countc，countd 计算重复解以前结果为超时，说明这种逐步搜索的方法对于独立的集合来说效率不足
class Solution
{
public:
int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D)
{
const int n = A.size();
int a, b, c, d, count, counta, countb, countc, countd;
sort(A.begin(), A.end()), sort(B.begin(), B.end()), sort(C.begin(), C.end()), sort(D.begin(), D.end()); for (a = count = ; a < n; a++)
{
if (A[a] + B[n - ] + C[n - ] + D[n - ] < ) // A[a] 过小
continue;
if (A[a] + B[] + C[] + D[] > ) // A[a] 过大
break;
for (counta = ; a < n - && A[a + ] == A[a]; a++, counta++);// A[a] 重复计数
for (b = ; b < n; b++)
{
if (A[a] + B[b] + C[n - ] + D[n - ] < ) // B[b] 过小
continue;
if (A[a] + B[b] + C[] + D[] > ) // B[b] 过大
break;
for (countb = ; b < n - && B[b + ] == B[b]; b++, countb++);// B[b] 重复计数
for (c = , d = n - ; c < n && d >= ;)
{
if (A[a] + B[b] + C[c] + D[d] < )
c++;
else if (A[a] + B[b] + C[c] + D[d] > )
d--;
else
{
for (countc = ; c < n - && C[c + ] == C[c]; c++, countc++);
for (countd = ; d > && D[d - ] == D[d]; d--, countd++);
count += counta * countb * countc * countd;
c++, d--;
}
}
}
}
return count;
}
};
● 大佬的解法，197 ms，unordered_map 查找
class Solution
{
public:
int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D)
{
unordered_map<int, int> abSum;
int count = ;
auto it = abSum.begin();
for (auto a : A)
{
for (auto b : B)
abSum[a + b]++;
}
for (auto c : C)
{
for (auto d : D)
{
if ((it = abSum.find( - c - d))!= abSum.end())
count += it->second;
}
}
return count;
}
};
● 大佬的解法，203 ms，二分查找
class Solution
{
public:
int biSearch(vector<int> & nums, int x, bool LEFT)// 在 nums 中搜索值为 x 的元素，由于存在重复元素，使用了两种二分搜索，用 LEFT 区分
{
int lp, rp, mp;
for (lp = , rp = nums.size() - , mp = (lp + rp) / ; lp <= rp; mp = (lp + rp) / )
{
if (LEFT)// 搜索最靠左的 x
{
if (nums[mp] >= x)
rp = mp - ;
else
lp = mp + ;
}
else // 搜索最靠右的 x
{
if (nums[mp] <= x)
lp = mp + ;
else
rp = mp - ;
}
}
return LEFT ? lp : rp;
}
int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D)
{
const int n = A.size();
vector<int> s, m;
int i, j, sum, ans;
for (i = ; i < n; i++)
{
for (j = ; j < n; j++)
s.push_back(A[i] + B[j]), m.push_back(C[i] + D[j]);
}
sort(s.begin(), s.end()), sort(m.begin(), m.end());
for (i = sum = ans = ; i < s.size(); ++i)
{
if (i != && s[i] == s[i - ])// 重复计数
ans += sum;
else
{
sum = biSearch(m, -s[i], false) - biSearch(m, -s[i], true) + ;// 第二个重复计数
ans += sum;
}
}
return ans;
}
};
▶ 第 657 题，n = 2，数据结构是中根二叉树
● 代码，38 ms，中根序遍历这棵树，把数字都取出来（恰好为升序数列），再用前面的方法计算
class Solution
{
public:
bool findTarget(TreeNode* root, int k)
{
vector<int> nums;
inorder(root, nums);
for (int i = , j = nums.size() - ; i < j;)
{
if (nums[i] + nums[j] == k)
return true;
(nums[i] + nums[j] < k) ? i++ : j--;
}
return false;
}
void inorder(TreeNode* root, vector<int>& nums)// 中根序遍历树
{
if (root == NULL)
return;
inorder(root->left, nums);
nums.push_back(root->val);
inorder(root->right, nums);
}
};
● 代码，38 ms，从树的中根序两端向中间遍历
class BSTIterator
{
private:
stack<TreeNode*> s;
bool forward;
public:
BSTIterator(TreeNode* root, bool forward)
{
for (this->forward = forward; root != nullptr; root = forward ? root->left : root->right)
s.push(root);
}
TreeNode* next()
{
if (s.empty())
return NULL;
TreeNode *top, *tmp;
for (top = s.top(), s.pop(), tmp = (forward ? top->right : top->left); tmp != nullptr; s.push(tmp), tmp = (forward ? tmp->left : tmp->right));
return top;
}
};
class Solution
{
public:
bool findTarget(TreeNode* root, int k)
{
int sum;
BSTIterator forward(root, true), backward(root, false);// 获取最前结点和最后结点（最小和最大元素）
TreeNode *fn, *bn;
for (fn = forward.next(), bn = backward.next(); fn != bn;)
{
sum = fn->val + bn->val;
if (sum == k)
return true;
(sum < k) ? (fn = forward.next()) : (bn = backward.next());
}
return false;
}
};