LeetCode 15超出时间复杂度！！
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
set<vector<int>> result;
vector<vector<int>> re;
for(int i = 0; i < nums.size(); i++)
{
int target = -nums[i];
unordered_map<int,int> hashtable;
for (int j = 0; j < nums.size(); j++)
{
if (j == i)
continue;
auto it = hashtable.find(target - nums[j]);
if (it != hashtable.end())
{ int Max = max(max(nums[i],it->first),max(it->first,nums[j]));
int Min = min(min(nums[i],it->first),min(it->first,nums[j]));
result.insert({Max,0-Max-Min,Min});
}
hashtable[nums[j]] = j;
};
}
for (auto &a: result)
{
re.push_back(a);
}
return re;
}
};
如何进行优化
https://blog.csdn.net/qq_48508278/article/details/124304543
我这个时间复杂度看上去也是O(n^2) 为啥过不了呢
不知道你这个问题是否已经解决, 如果还没有解决的话:亓官劼的博客 ，同时正在尝试在B站中做一些内容分享，B站主页为： 亓官劼的B站主页大家好，我叫亓官劼（qí guān jié ），在CSDN中记录学习的点滴历程，时光荏苒，未来可期，加油~博主目前仅在CSDN中写博客，唯一博客更新的地址为：
本文原创为亓官劼，请大家支持原创，部分平台一直在恶意盗取博主的文章！！！
若需联系博主，可以联系本人微信：qiguanjie2015
给你两个长度相同的字符串，s 和 t。
将 s 中的第 i 个字符变到 t 中的第 i 个字符需要 |s[i] - t[i]| 的开销（开销可能为 0），也就是两个字符的 ASCII 码值的差的绝对值。
用于变更字符串的最大预算是 maxCost。在转化字符串时，总开销应当小于等于该预算，这也意味着字符串的转化可能是不完全的。
如果你可以将 s 的子字符串转化为它在 t 中对应的子字符串，则返回可以转化的最大长度。
如果 s 中没有子字符串可以转化成 t 中对应的子字符串，则返回 0。
示例 1：
输入：s = "abcd", t = "bcdf", cost = 3
输出：3
解释：s 中的 "abc" 可以变为 "bcd"。开销为 3，所以最大长度为 3。
示例 2：
输入：s = "abcd", t = "cdef", cost = 3
输出：1
解释：s 中的任一字符要想变成 t 中对应的字符，其开销都是 2。因此，最大长度为 1。
示例 3：
输入：s = "abcd", t = "acde", cost = 0
输出：1
解释：你无法作出任何改动，所以最大长度为 1。
提示：
1 <= s.length, t.length <= 10^50 <= maxCost <= 10^6s 和 t 都只含小写英文字母。针对LeetCode 15问题的时间复杂度优化，可以使用双指针的方法来解决。具体步骤如下： 1. 首先对两个链表进行初始化，一个代表第一个链表的头节点，另一个代表第二个链表的头节点。同时定义一个结果链表的头节点和一个指针指向结果链表的当前节点。 2. 对两个链表进行遍历，同时将两个链表的节点值相加，并将结果添加到结果链表中。累加的值如果超过10，需要进位。 3. 如果其中一个链表遍历完，但另一个链表还没有遍历完，则需要将剩余的节点值继续相加，并添加到结果链表中。 4. 最后需要判断最后一次相加的结果是否需要进位，如果需要进位，则在结果链表中添加一个值为1的节点。 5. 返回结果链表的头节点。
下面是具体的代码实现：
#include <iostream>
#include <stack>
using namespace std;
// 链表节点结构体
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
// 结果链表的头节点
ListNode* result = new ListNode(0);
// 结果链表的当前节点指针
ListNode* curr = result;
// 进位值
int carry = 0;
// 双指针遍历两个链表
while (l1 || l2) {
// 遍历第一个链表
int x = l1 ? l1->val : 0;
// 遍历第二个链表
int y = l2 ? l2->val : 0;
// 两个链表的节点值相加，再加上进位值
int sum = x + y + carry;
// 更新进位值
carry = sum / 10;
// 创建新的节点，并将计算结果添加到结果链表中
curr->next = new ListNode(sum % 10);
// 移动指针
curr = curr->next;
if (l1) l1 = l1->next;
if (l2) l2 = l2->next;
}
// 判断最后一次相加的结果是否需要进位
if (carry > 0) {
curr->next = new ListNode(carry);
}
return result->next;
}
// 创建链表
ListNode* createList(int arr[], int n) {
if (n == 0) return NULL;
ListNode* head = new ListNode(arr[0]);
ListNode* curr = head;
for (int i = 1; i < n; i++) {
curr->next = new ListNode(arr[i]);
curr = curr->next;
}
return head;
}
// 打印链表
void printList(ListNode* head) {
ListNode* curr = head;
while (curr) {
cout << curr->val;
if (curr->next) cout << " -> ";
curr = curr->next;
}
cout << endl;
}
int main() {
int arr1[] = {2, 4, 3};
int arr2[] = {5, 6, 4};
ListNode* l1 = createList(arr1, sizeof(arr1) / sizeof(arr1[0]));
ListNode* l2 = createList(arr2, sizeof(arr2) / sizeof(arr2[0]));
ListNode* result = addTwoNumbers(l1, l2);
printList(result);
delete l1;
delete l2;
delete result;
return 0;
}
这样可以将LeetCode 15问题的时间复杂度从O(n^2)优化为O(n)，提高了算法的效率。