Leetcode_hot100_day1
目录
Leetcode_hot100_day1
[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 。提示：
3 <= nums.length <= 3000-105 <= nums[i] <= 105
分析：
先排序，固定最小的加数，然后用双指针去夹住后面的序列，去查看三数之和是大了还是小了，决定指针往左还是往右移动。这里要注意的是记得去重，这里调了好久。
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> res;
for (int k = 0; k < nums.size(); k++) {
if (nums[k] > 0)
break;
if (k > 0 && nums[k] == nums[k - 1])
continue;
int i = k + 1, j = nums.size() - 1;
while (i < j) {
if (nums[i] + nums[j] + nums[k] == 0) {
res.push_back({nums[i], nums[j], nums[k]});
while(i<j&&nums[i]==nums[i+1])///答案去重这里，有点难
i++;
while(i<j&&nums[j]==nums[j-1])
j--;
i++;//注意
j--;
} else if (nums[i] + nums[j] + nums[k] > 0)
j--;
else
i++;
}
}
return res;
}
};[3. 无重复字符的最长子串]
( )
已解答
中等
相关标签
相关企业
提示
给定一个字符串
s
，请你找出其中不含有重复字符的
最长 子串
的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。提示：
0 <= s.length <= 5 * 104s由英文字母、数字、符号和空格组成
分析：
很合理的思路，但是最后一个样例不能通过。暴力，但是我并不觉得很暴力，感觉还是很优美哈哈，986 / 987 个通过的测试用例。
class Solution {
public:
bool checkNor(string s){
unordered_map<char,int> h;
for(int i=0;i<s.length();i++){
h[s[i]]++;
if(h[s[i]]>1)
return false;
}
return true;
}
int lengthOfLongestSubstring(string s) {
int ans=0;
for(int i=0; i < s.length(); ){
int j=i+1;
string tmp=s.substr(i,j-i);
while(checkNor(tmp)){
ans=ans>tmp.length()?ans:tmp.length();
j++;
if(j> s.length())
break;
tmp=s.substr(i,j-i);
}
i++;
}
return ans;
}
};然后我让gpt优化了一下，以为能通过，其实还是没有，但是优化一下的代码更优美，尤其是去重那部分。
class Solution {
public:
// 优化 checkNor，不再创建新的字符串，而是直接在 s 上检查
bool checkNor(const string &s, int start, int end) {
unordered_set<char> h;
for (int i = start; i < end; i++) {
if (h.count(s[i])) return false; // 如果已有字符，返回 false
h.insert(s[i]);
}
return true;
}
int lengthOfLongestSubstring(string s) {
int ans = 0;
for (int i = 0; i < s.length(); i++) {
int j = i + 1;
while (j <= s.length() && checkNor(s, i, j)) { // 直接在 s 上检查，避免 substr
ans = max(ans, j - i);
j++;
}
}
return ans;
}
};然后屈服了，去学习一下，是怎么个事儿。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_set<char> lookup;
int ans=0;
int left=0;
for(int i=0;i<s.length();i++){
while(lookup.find(s[i])!=lookup.end()){//找到了
//窗口向右滑动，直到s[i]在窗口内不重复
lookup.erase(s[left]);
left++;
}
//没找到右边界的，可以插入
lookup.insert(s[i]);
ans=max(ans,i-left+1);
}
return ans;
}
};