1.Two Sum

Description of the problem

  • 双循环遍历

时间复杂度：O(n2)O(n^2)

空间复杂度：O(1)O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int>ans;
        for(int i=0;i<nums.size()-1;i++){
            for(int j=i+1;j<nums.size();j++){
                if(nums[i]+nums[j]==target){
                    ans.push_back(i);
                    ans.push_back(j);
                    break;
                }
            }
        }
        return ans;
    }
};
  • 哈希表

时间复杂度：O(n)O(n)

空间复杂度：O(n)O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int>mp;
        for(int i=0;i<nums.size();++i){
            int com=target-nums[i];
            if(mp.find(com)!=mp.end()){
                return {mp[com],i};
            }
            mp[nums[i]]=i;
        }
        return {};
    }
};

Add Two Numbers

Description of the problem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* d=new ListNode(0);
        ListNode* c=d;
        int have=0;

        while(l1!=nullptr||l2!=nullptr||have){
            int sum=have;
            if(l1){
                sum+=l1->val;
                l1=l1->next;
            }
            if(l2){
                sum+=l2->val;
                l2=l2->next;
            }
            have=sum/10;
            c->next=new ListNode(sum%10);
            c=c->next;
        }

        return d->next;
    }
};

Longest Substring Without Repeating Characters

Description of the problem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//滑动窗口
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int ans=0;

        unordered_map<char,int>index;
        int k=0;
        for(int i=0;i<s.size();++i){
            if(index.count(s[i])&&index[s[i]]>=k){
                k=index[s[i]]+1;
            }
            index[s[i]]=i;
            ans=max(ans,i-k+1);
        }
        return ans;
    }
};

Median of Two Sorted Arrays

Description of the problem

1