1.两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。示例 1：输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：输入：nums = [3,2,4], target = 6 输出：[1,2]
示例 3：输入：nums = [3,3], target = 6 输出：[0,1]
思路:
1.哈希表记录存在性
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int,int> hash;
for (int i = 0; i < nums.size(); ++i) {
auto it = hash.find(target - nums[i]);
if (it != hash.end()) {
return {it->second, i};
}
hash[nums[i]] = i;
}
return {};
}
};
170.两数之和 III - 数据结构设计
设计一个接收整数流的数据结构，该数据结构支持检查是否存在两数之和等于特定值。
实现 TwoSum 类：
TwoSum() 使用空数组初始化 TwoSum 对象
void add(int number) 向数据结构添加一个数 number
boolean find(int value) 寻找数据结构中是否存在一对整数，使得两数之和与给定的值相等。如果存在，返回 true ；否则，返回 false 。示例：输入：
[“TwoSum”, “add”, “add”, “add”, “find”, “find”]
[[], [1], [3], [5], [4], [7]]
输出：
[null, null, null, null, true, false]
解释：
TwoSum twoSum = new TwoSum();
twoSum.add(1); // [] —> [1]
twoSum.add(3); // [1] —> [1,3]
twoSum.add(5); // [1,3] —> [1,3,5]
twoSum.find(4); // 1 + 3 = 4，返回 true
twoSum.find(7); // 没有两个整数加起来等于 7 ，返回 false
分析:
1.处理[0], [0]这种case和处理[0]这种case一个返回true, 一个是false, 需要额外判断出现的次数
class TwoSum {
private:
unordered_map<long, int> hash;
public:
TwoSum() {
}
void add(int number) {
unordered_map<long, int>::iterator it = hash.find(number);
if (it == hash.end()) {
hash[number] = 1;
} else {
++hash[number];
}
return;
}
bool find(int value) {
for (unordered_map<long, int>::iterator it = hash.begin(); it != hash.end(); ++it) {
long complement = value - it->first;
if (hash.find(complement) != hash.end()) {
if (complement != it->first) {
return true;
} else {
if (hash[complement] > 1) {
return true;
}
}
}
}
return false;
}
};
167.两数之和 II - 输入有序数组
给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。你所设计的解决方案必须只使用常量级的额外空间。示例 1：输入：numbers = [2,7,11,15], target = 9 输出：[1,2] 解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
示例 2：输入：numbers = [2,3,4], target = 6 输出：[1,3] 解释：2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。
示例 3：输入：numbers = [-1,0], target = -1 输出：[1,2] 解释：-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
解法:
1.先二分搜索加快双指针搜索效率
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int left = 0;
int right = numbers.size()-1;
while (left < right) {
int mid = left + (right - left) / 2;
if (numbers[left] + numbers[right] == target) {
return {left+1, right+1};
} else {
if (numbers[left] + numbers[mid] > target) {
right = mid;
} else if (numbers[mid] + numbers[right] < target) {
left = mid;
} else if (numbers[left] + numbers[right] < target) {
++left;
} else if (numbers[left] + numbers[right] > target) {
--right;
}
}
}
return {};
}
};
1099.小于 K 的两数之和
给你一个整数数组 nums 和整数 k ，返回最大和 sum ，满足存在 i < j 使得 nums[i] + nums[j] = sum 且 sum < k 。如果没有满足此等式的 i,j 存在，则返回 -1 。
示例 1：输入：nums = [34,23,1,24,75,33,54,8], k = 60 输出：58 解释：34 和 24 相加得到 58，58 小于 60，满足题意。
示例 2：输入：nums = [10,20,30], k = 15 输出：-1 解释：我们无法找到和小于 15 的两个元素。
分析:
1.双指针夹逼
class Solution {
public:
int twoSumLessThanK(vector<int>& nums, int k) {
int n = nums.size();
if (n < 2) {
return -1;
}
sort(nums.begin(), nums.end());
int left = 0;
int right = n - 1;
int sum = -1;
while (left < right) {
if (nums[left] + nums[right] >= k) {
--right;
} else {
sum = max(sum, nums[left] + nums[right]);
++left;
}
}
return sum;
}
};
15.三数之和
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。 注意：答案中不可以包含重复的三元组。
示例 1：输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。示例 2：输入：nums = [0,1,1] 输出：[] 解释：唯一可能的三元组和不为 0 。
示例 3：输入：nums = [0,0,0] 输出：[[0,0,0]] 解释：唯一可能的三元组和为 0 。
分析:
1.因为只是判断存在性, 元素前后不存在先后顺序, 所以先排序
2.对所有的元素扫描, 固定住当前的第 i 个元素, 在后面的数组用双指针搜索 complement == nums[left] + nums[right] == - nums[i] 的情况
3.因为我们要的结果是不重复的三元组, 如果当前的元素和前面的一个元素相等, 就会多计算一次, 所以在找的时候直接过掉这一次; 在左右指针搜索的时候, 也要注意避免重复的结果 push
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> ans;
int len = nums.size();
if (len <= 2) {
return ans;
}
sort(nums.begin(), nums.end());
// 当前元素作为最小的元素
for (int i = 0; i < len - 2; ++i) {
// 最小的元素>0, 后面都不用搜索了
if (nums[i] > 0) {
break;
}
// 如果当前元素和前面元素相同, 不再重复判断, 否则会造成结果重复
if (i - 1 >= 0 && nums[i] == nums[i-1]) {
continue;
}
int complement = -nums[i];
int left = i + 1;
int right = len - 1;
while (left < right) {
if (nums[left] + nums[right] == complement) {
ans.push_back({nums[i], nums[left], nums[right]});
while (left < right && nums[left] == nums[left+1]) {
++left;
}
while (left < right && nums[right] == nums[right-1]) {
--right;
}
++left;
--right;
} else if (nums[left] + nums[right] < complement) {
++left;
} else if (nums[left] + nums[right] > complement) {
--right;
}
}
}
return ans;
}
};
259.较小的三数之和
给定一个长度为 n 的整数数组和一个目标值 target ，寻找能够使条件 nums[i] + nums[j] + nums[k] < target 成立的三元组 i, j, k 个数（0 <= i < j < k < n）。
示例 1：输入: nums = [-2,0,1,3], target = 2 输出: 2 解释: 因为一共有两个三元组满足累加和小于 2: [-2,0,1] [-2,0,3]
示例 2：输入: nums = [], target = 0 输出: 0
示例 3：输入: nums = [0], target = 0 输出: 0
分析:
1.先排序
2.固定住第一个元素, 然后用左右指针的思想, 累计满足条件的个数
class Solution {
public:
int threeSumSmaller(vector<int>& nums, int target) {
int ans = 0;
int n = nums.size();
if (n < 3) {
return ans;
}
sort(nums.begin(), nums.end());
int left;
int right;
for (int i = 0; i < n - 2; ++i) {
left = i + 1;
right = n - 1;
while (left < right) {
if (nums[i] + nums[left] + nums[right] < target) {
ans += right - left;
++left;
} else {
--right;
}
}
}
return ans;
}
};
16.最接近的三数之和
给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在恰好一个解。
示例 1：输入：nums = [-1,2,1,-4], target = 1 输出：2 解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
示例 2：输入：nums = [0,0,0], target = 1 输出：0
分析:
1.排序之后, 双指针逼近
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
int ans = nums[0];
int n = nums.size();
int minDiff = INT_MAX;
int diff;
int sum;
int left;
int right;
sort(nums.begin(), nums.end());
for (int i = 0; i < n - 2; ++i) {
left = i + 1;
right = n - 1;
while (left < right) {
sum = nums[i] + nums[left] + nums[right];
int diff = abs(sum - target);
if (diff < minDiff) {
minDiff = diff;
ans = sum;
}
if (sum == target) {
return ans;
} else if (sum < target) {
++left;
} else if (sum > target) {
--right;
}
}
}
return ans;
}
};
18.四数之和
给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。示例 1：输入：nums = [1,0,-1,0,-2,2], target = 0 输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2：输入：nums = [2,2,2,2,2], target = 8 输出：[[2,2,2,2]]
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
}
};
转载请注明来源, from goldandrabbit.github.io
