题目
1 两数之和
167 两数之和 II - 输入有序数组
599 两个列表的最小索引总和
219 存在重复元素 II
220 存在重复元素 III
1 两数之和
给定一个整数数组 $nums$ 和一个整数目标值 $target$，请你在该数组中找出 和为目标值 $target$ 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
题解
假设两个整数分别为 x, y，则y亦可表示为 $target-x$
暴力枚举，注意到对于每一个 $x$，其都有可能出现跟它匹配的$y$，使用两遍for枚举。最差的情况为
$$ 1+2+...+(n-2)+(n-1)=n^2/2 $$
即时间复杂度为$O(n^2)$
使用哈希表，使用哈希表可以将查找时间从$O(n)$ 下降到 $O(1)$。两个整数，总是先后出现，因此我们无需纠结哪个先出现。首先建一个哈希表，对于遍历到的每一个$i$，查询哈希表中是否存在$y$（即$target-x$），是则直接返回两数坐标，否则将 $x$ 插入到哈希表中，这样的先后顺序保证了 $x$ 不会与自己匹配。
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int, int> hashMap; for(int i=0;i<nums.size(); i++) { auto iter= hashMap.find(target-nums[i]); if(iter!=hashMap.end()) { return {i,iter->second}; } hashMap[nums[i]]=i; } return {}; } };该情况下，哈希表查找的时间开销为$O(1)$，整体的时间复杂度为$O(n)$，空间复杂度为$O(n)$。
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] 。提示：
- $2 <= numbers.length <= 3 * 104$
- $-1000 <= numbers[i] <= 1000$
- $numbers$ 按 非递减顺序 排列
- $-1000 <= target <= 1000$
- 仅存在一个有效答案
题解
用上一题的方法解，注意下标从1开始
class Solution { public: vector<int> twoSum(vector<int>& numbers, int target) { unordered_map<int, int> hashMap; for(int i=0;i<numbers.size(); i++) { auto iter= hashMap.find(target-numbers[i]);//查找键 if(iter!=hashMap.end()) { return {iter->second+1,i+1};//numbers[i+1]位置在后面 } hashMap[numbers[i]]=i;//<值，位置> } return {}; } };
二分查找：
for(int i=0;i<numbers.size();i++) { int low=i+1; int high=numbers.size()-1; while(low<=high) { int mid=low+(high-low)/2; if(numbers[mid]==target-numbers[i])//找到 { return {i+1,mid+1}; } else if(numbers[mid]>target-numbers[i])//在左边 { high=mid-1; } else//在右边 { low=mid+1; } } } return {-1,-1};双指针法
初始时两个指针分别指向第一个元素位置和最后一个元素的位置。每次计算两个指针指向的两个元素之和，并和目标值比较。如果两个元素之和等于目标值，则发现了唯一解。如果两个元素之和小于目标值，则将左侧指针右移一位。如果两个元素之和大于目标值，则将右侧指针左移一位。移动指针之后，重复上述操作，直到找到答案。
使用双指针的实质是缩小查找范围。那么会不会把可能的解过滤掉？答案是不会。假设 $numbers[i]+numbers[j]=target$ 是唯一解，其中 $0≤i<j≤numbers.length−1$。初始时两个指针分别指向下标 $0$ 和下标 $numbers.length−1$，左指针指向的下标小于或等于 i，右指针指向的下标大于或等于 j。除非初始时左指针和右指针已经位于下标 i 和 j，否则一定是左指针先到达下标 i 的位置或者右指针先到达下标 j 的位置。
- 如果左指针先到达下标 i 的位置，此时右指针还在下标 j 的右侧，$sum>target$，因此一定是右指针左移，左指针不可能移到 iii 的右侧。
- 如果右指针先到达下标 jjj 的位置，此时左指针还在下标 iii 的左侧，$sum<target$，因此一定是左指针右移，右指针不可能移到 j 的左侧。
由此可见，在整个移动过程中，左指针不可能移到 i 的右侧，右指针不可能移到 j 的左侧，因此不会把可能的解过滤掉。由于题目确保有唯一的答案，因此使用双指针一定可以找到答案。
int i=0; int j=numbers.size()-1; while (i<j) { if(numbers[i]+numbers[j]==target) return {i+1,j+1}; else if(numbers[i]+numbers[j] > target) { j--; } else { i++; } } return {-1,-1};
使用非递减顺序排列，即递增顺序数组，且每一个
599 两个列表的最小索引总和
假设 Andy 和 Doris 想在晚餐时选择一家餐厅，并且他们都有一个表示最喜爱餐厅的列表，每个餐厅的名字用字符串表示。
你需要帮助他们用最少的索引和找出他们共同喜爱的餐厅。 如果答案不止一个，则输出所有答案并且不考虑顺序。 你可以假设答案总是存在。
示例与提示
示例 1:
输入: list1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"]，list2 = ["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"]
输出: ["Shogun"]
解释: 他们唯一共同喜爱的餐厅是“Shogun”。示例 2:
输入:list1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"]，list2 = ["KFC", "Shogun", "Burger King"]
输出: ["Shogun"]
解释: 他们共同喜爱且具有最小索引和的餐厅是“Shogun”，它有最小的索引和1(0+1)。提示:
- $1 <= list1.length, list2.length <= 1000$
- $1 <= list1[i].length, list2[i].length <= 30$
- $list1[i]$ 和 $list2[i]$ 由空格 $' '$ 和英文字母组成。
- $list1$ 的所有字符串都是 唯一 的。
- $list2$ 中的所有字符串都是 唯一 的。
题解
使用一个哈希表记录 $list1$ 中每一个餐厅对应的索引下标，然后遍历 $list2$ 中的餐厅名称，若该名称在 $list1$ 中存在，且：
- 该名称下标索引之和小于当前结果，则清空结果，将该名称加入结果中；
- 该名称下标索引之和等于当前结果，则将该名称加入结果中。
否则继续遍历，遍历 $list2$ 的时候，若当前索引大于当前最小索引和，则退出，不再需要判断。
class Solution {
public:
vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {
unordered_map<string, int> indexMap;
vector<string> result;
int indexSum=__INT_MAX__;
for(int i=0;i<list1.size();i++)
{
indexMap[list1[i]]=i;
}
for(int j=0;j<list2.size();j++)
{
if(j>indexSum)break;
if(indexMap.count(list2[j])>0)
{
int k = indexMap[list2[j]];
if(j+k<indexSum)
{
result.clear();
result.push_back(list2[j]);
indexSum=j+k;
}
else if(j+k==indexSum)
{
result.push_back(list2[j]);
}
}
}
return result;
}
};219 存在重复元素II
给你一个整数数组 $nums$ 和一个整数 $k$ ，判断数组中是否存在两个 不同的索引 $i$ 和 $j$ ，满足 $nums[i] == nums[j]$ 且 $abs(i - j) <= k$ 。如果存在，返回 $true$ ；否则，返回 $false$ 。
示例 1：
输入：nums = [1,2,3,1], k = 3
输出：true示例 2：
输入：nums = [1,0,1,1], k = 1
输出：true示例 3：
输入：nums = [1,2,3,1,2,3], k = 2
输出：false提示：
- $1 <= nums.length <= 10^5$
- $-10^9 <= nums[i] <= 10^9$
- $0 <= k <= 10^5$
题解
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
unordered_set<int> w;
int length=nums.size();
for(int i=0;i<length;i++)
{
if(i>k)
{
w.erase(nums[i-k-1]);
}
if(w.count(nums[i]))
{
return true;
}
w.emplace(nums[i]);//加入新的元素
}
return false;
}
};220 存在重复元素III
给你一个整数数组 $nums$ 和两个整数 $k$ 和 $t$ 。请你判断是否存在 两个不同下标 $i$ 和 $j$，使得 $abs(nums[i] - nums[j]) <= t$ ，同时又满足 $abs(i - j) <= k$ 。
如果存在则返回 $true$，不存在返回 $false$。
示例 1：
输入：nums = [1,2,3,1], k = 3, t = 0
输出：true示例 2：
输入：nums = [1,0,1,1], k = 1, t = 2
输出：true示例 3：
输入：nums = [1,5,9,1,5,9], k = 2, t = 3
输出：false提示：
- $0 <= nums.length <= 2 * 10^4$
- $-2^{31} <= nums[i] <= 2^{31} - 1$
- $0 <= k <= 10^4$
- $0 <= t <= 2^{31} - 1$
题解
我们也可以使用利用桶排序的思想解决本题。我们按照元素的大小进行分桶，维护一个滑动窗口内的元素对应的元素。
对于元素 x，其影响的区间为$[x−t,x+t]$。于是我们可以设定桶的大小为 t+1。如果两个元素同属一个桶，那么这两个元素必然符合条件。如果两个元素属于相邻桶，那么我们需要校验这两个元素是否差值不超过 t。如果两个元素既不属于同一个桶，也不属于相邻桶，那么这两个元素必然不符合条件。
具体地，我们遍历该序列，假设当前遍历到元素 x，那么我们首先检查 x 所属于的桶是否已经存在元素，如果存在，那么我们就找到了一对符合条件的元素，否则我们继续检查两个相邻的桶内是否存在符合条件的元素。
实现方面，我们将 int 范围内的每一个整数 x 表示为 $x=(t+1)×a+b(0≤b≤t)$ 的形式，这样 x 即归属于编号为 a 的桶。因为一个桶内至多只会有一个元素，所以我们使用哈希表实现即可。
链接
/*
* @lc app=leetcode.cn id=220 lang=cpp
*
* [220] 存在重复元素 III
*/
// @lc code=start
class Solution {
public:
int getID(int x, long w)
{
return x < 0 ? (x+1ll) / w-1:x/w;
}
bool containsNearbyAlmostDuplicate(vector<int>& nums, int indexDiff, int valueDiff) {
unordered_map<int, int> map;
int n = nums.size();
for(int i = 0;i<n;i++)
{
long x= nums[i];
int id= getID(x,valueDiff+1ll);
if(map.count(id))
{
return true;
}
if(map.count(id-1)&&abs(x-map[id-1])<=valueDiff)
{
return true;
}
if(map.count(id+1)&&abs(x-map[id+1])<=valueDiff)
{
return true;
}
map[id]=x;
if(i>=indexDiff)
{
map.erase(getID(nums[i-indexDiff],valueDiff+1ll));
}
}
return false;
}
};
// @lc code=end
