2sum，找两数之和等于t
- https://leetcode.com/problems/two-sum/
数组无序，可以用个unordered_map记录出现过的数，对当前数看map中是否存在toFind=t-nums[i]。
- https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/
数组有序，可以两指针相向遍历。若a[i]+a[j]==t则找到，<t则右移i，>t则左移j。
- https://leetcode.com/problems/two-sum-iv-input-is-a-bst/
在bst中找两数之和等于t，可以直接像无序数组那样用个unordered_set记录出现过的数，dfs一遍。
某数能否分解成两数的平方和
[1..sqrt(num)]上，两指针相向遍历
4个数组各取一数之和等于0，有多少种取法
取两数组作为一组，用cnt[]给和计数，类似无序数组的2sum问题
3sum，找三数之和等于t
数组排序，在2sum问题的外层加个循环遍历取第一个数。
- https://leetcode.com/problems/3sum/
- https://leetcode.com/problems/3sum-closest/
- https://leetcode.com/problems/3sum-smaller/
- https://leetcode.com/problems/valid-triangle-number/
Given an array of n integers nums and a target, find the number of index triplets
i, j, kwith0 <= i < j < k < nthat satisfy the conditionnums[i] + nums[j] + nums[k] < target.For example, given nums =
[-2, 0, 1, 3], and target = 2.Return 2. Because there are two triplets which sums are less than 2:
[-2, 0, 1] [-2, 0, 3]Follow up:
Could you solve it in O(n^2) runtime?
int threeSumSmaller(vector<int>& nums, int target) {
// 两指针法
sort(nums.begin(), nums.end());
const int N = nums.size();
int ans = 0;
for (int i = 0; i < N - 2; i++) {
int j = i + 1, k = N - 1;
while (j < k) {
if (nums[i] + nums[j] + nums[k] < target) {
// j&k, j&(k-1), j&(k-2) ... j&(j+1) 的数对都满足
ans += k - j;
j++;
} else {
k--;
}
}
}
return ans;
}
可作三角形边长的三数有多少组
- https://leetcode.com/problems/valid-triangle-number/ 类似3sums-smaller
int triangleNumber(vector<int>& nums) {
sort(nums.begin(), nums.end());
const int N = nums.size();
int ans = 0;
for (int k = 2; k < N; k++) {
int i = 0, j = k - 1;
while (i < j) {
if (nums[i] + nums[j] > nums[k]) {
// (i,j) & (i+1,j) & ... & (j-1,j) 都符合
ans += j - i;
j--;
} else {
i++;
}
}
}
return ans;
}