首页 > 代码库 > leetcode-7-basic
leetcode-7-basic
解题思路：
这道题需要注意的是s和t长度相等，但都为空的情况。只需要扫描一遍s建立字典（char, count），然后扫描t，如果有
未出现的字母，或者键值小于0，就可以返回false了。
bool isAnagram(string s, string t) {
if (s.length() != t.length())
return false;
if (s.length() == 0 && t.length() == 0)
return true;
map<char,int> dict;
for (int i = 0; i < s.length(); i++) {
if (dict.find(s[i]) == dict.end()) {
dict.insert(dict.end(), make_pair(s[i],1));
} else
dict.find(s[i])->second++;
}
for (int i = 0; i < t.length(); i++) {
if (dict.find(t[i]) == dict.end())
return false;
else {
dict.find(t[i])->second--;
if (dict.find(t[i])->second < 0)
return false;
}
}
return true;
}
但是，因为题目中说是小写字母，所以可以用数组来做。思路类似，相比使用map插入更简单。
bool isAnagram(string s, string t) {
if (s.length() != t.length()) return false;
int n = s.length();
int counts[26] = {0};
for (int i = 0; i < n; i++) {
counts[s[i] - ‘a‘]++;
counts[t[i] - ‘a‘]--;
}
for (int i = 0; i < 26; i++)
if (counts[i]) return false;
return true;
}
解题思路：
本来是用遍历两次数组来算的，外层0~n-1，内层i+1~n-1，找到即跳出。但是如果数组很大，这样无疑很耗时。
由于数组是升序，所以考虑从左右两端开始查找。如果numbers[left]+numbers[right]==target，就找到了；
大于的话right左移，小于的话left右移。当left>=right时，终止。
vector<int> twoSum(vector<int>& numbers, int target) {
vector<int> result;
int left = 0;
int right = numbers.size() - 1;
while(left < right) {
if (numbers[left] + numbers[right] == target) {
result.push_back(left + 1);
result.push_back(right + 1);
break;
}
else if (numbers[left] + numbers[right] > target) {
right --;
}
else {
left ++;
}
}
return result;
}
leetcode-7-basic
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。