网站模板和源码区别,西安网站建设网站排名优化,网站建设属于高新技术收入吗,网站建设方案产业1. 两数之和 - 力扣#xff08;LeetCode#xff09;
暴力解法#xff1a; O ( N 2 ) O(N^2) O(N2)遍历数组#xff0c;找两个数相加为target O ( N ) O(N) O(N)解法#xff1a;将所有数排序#xff0c;并记录这些数的下标#xff0c;双指针从左右向中间走。指向的两数…1. 两数之和 - 力扣LeetCode
暴力解法 O ( N 2 ) O(N^2) O(N2)遍历数组找两个数相加为target O ( N ) O(N) O(N)解法将所有数排序并记录这些数的下标双指针从左右向中间走。指向的两数相加大于target则r–小于则l第一对相等的数即为答案。 当然用二分、哈希也是可以的不过时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)
贴双指针解法证明很简单思考为什么双指针不会移动到两个答案之间反证一下就出来了
class Solution {typedef pairint, int PII;
public:vectorint twoSum(vectorint nums, int target) {vectorint ans(2);vectorPII a;for (int i 0; i nums.size(); i) {a.push_back({ nums[i], i });}sort(a.begin(), a.end());int l 0, r nums.size() - 1;while (l r) {if (a[l].first a[r].first target) {r -- ;}else if (a[l].first a[r].first target) {l ;}else {ans[0] a[l].second, ans[1] a[r].second;return ans;}}return ans;}
};49. 字母异位词分组 - 力扣LeetCode
若单词重新排列后和某个单词相同则分为一组 可以确定的是将所有单词中的字符升序排序后将出现多个相同单词这些单词作为“字母异位词”分为一组 对于每个单词将其升序排序用map记录该单词所位于的组号若无记录则作为新组
class Solution {
public:vectorvectorstring groupAnagrams(vectorstring strs) {vectorvectorstring ans;unordered_mapstring, int mp;for (int i 0; i strs.size(); i) {string s strs[i];sort(s.begin(), s.end());if (mp.count(s) 0) {mp[s] ans.size();ans.push_back(vectorstring());}ans[mp[s]].push_back(strs[i]);}return ans;}
};
