1.两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

1
2
3
4
5
6
7
8
9
10
vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int,int> map;
    for(int i=0;i<nums.size();i++){
        auto it=map.find(target-nums[i]);
        if(it!=map.end())
            return {i,it->second};
        map[nums[i]]=i;
    }
    return {};
}

2.两数相加

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0开头。

示例 1：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    int len1=1;//记录l1的长度
    int len2=1;//记录l2的长度
    ListNode* p1=l1;
    ListNode* p2=l2;
    while(p1->next != nullptr)//获取l1的长度
        {
            len1++;
            p1=p1->next;
        }
    while(p2->next != nullptr)//获取l2的长度
        {
            len2++;
            p2=p2->next;
        }
    if(len1>len2)//l1较长，在l2末尾补零
            for(int i=1;i<=len1-len2;i++)
            {
                p2->next=new ListNode(0);
                p2=p2->next;
            }
    else//l2较长，在l1末尾补零
        for(int i=1;i<=len2-len1;i++)
            {
                p1->next=new ListNode(0);
                p1=p1->next;
            }
    p1=l1;
    p2=l2;
    bool carry=false;//记录进位
    ListNode* l3=new ListNode(-1);//存放结果的链表
    ListNode* p3=l3;//l3的移动指针
    int res=0;//记录相加结果
    while(p1 != nullptr && p2 != nullptr)
        {
            res= carry + p1->val + p2->val;
            p3->next=new ListNode(res % 10);
            if(res >= 10) carry= true;
            else carry= false;
            p1=p1->next;
            p2=p2->next;
            p3=p3->next;
        }
        if(carry)//若最后还有进位
        {
            p3->next=new ListNode(1);
            p3=p3->next;
        }
        return l3->next;
    }

3.无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。
示例 1:
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int lengthOfLongestSubstring(string s) {
    // 滑动窗口思想
    unordered_set<char> set;// 哈希集合，记录每个字符是否出现过
    int len=s.length();
    // 右指针
    int right=-1;
    int res=0;
    for(int i=0;i<len;i++){
        if(i>0) set.erase(s[i-1]);// 左指针向右移动一格，移除一个字符
        while(right+1<len&&!set.count(s[right+1])){
            // 右指针不断移动
            set.insert(s[right+1]);
            right++;}
        // 第i到right个字符是一个最长无重复字符子串
        res=max(res,right-i+1);
    }
    return res;
}

4.最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
示例 1：
输入：s = “babad”
输出：”bab”
解释：”aba” 同样是符合题意的答案。

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
int expendCenter(string s,int left,int right)
//计算以left和right为中心的回文串长度
{
    int L=left;
    int R=right;
    while(L>=0 && R<s.length() && s[R]==s[L])
    {
        L--;
        R++;
    }
    return R-L-1;
}
string longestPalindrome(string s) {
    int len=s.length();
    // 保存回文子串的起始位置
    int begin=0;
    // 保存回文子串的结束位置
    int end=0;
    // 保存回文子串的最大长度
    int maxLen=0;
    for(int i=0;i<len;i++){
        // 一个元素为中心的情况
        int len1= expendCenter(s,i,i);
        // 两个元素为中心的情况
        int len2= expendCenter(s,i,i+1);
        maxLen=max(max(len1,len2),maxLen);
        if(maxLen>end-begin+1)
        {// 获取最新回文子串的开始和结束位置
            begin=i-(maxLen-1)/2;
            end=i+maxLen/2;
        }
    }
    string res=s.substr(begin,maxLen);
    return res;
}

5.盛最多水的容器

给定一个长度为 n 的整数数组height。有n条垂线，第 i 条线的两个端点是(i, 0)和(i, height[i])
找出其中的两条线，使得它们与x轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。
https://aliyun-lc-upload.oss-cn-hangzhou.aliyuncs.com/aliyun-lc-upload/uploads/2018/07/25/question_11.jpg
输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为49。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int maxArea(vector<int>& height) {
    int left=0;
    int right=height.size()-1;
    int res=0;
    while(left<right){
        if(height[left]<height[right])
// 注意：必须是(right-left)放前面，否则在height[left++]结束后，left已经自增1了
            res=max(res,(right-left)*height[left++]);
        else
            res=max(res,(right-left)*height[right--]);
    }
    return res;
}
// 初始化两边指针，移动时无论长板或短板向中间收窄一格，都会导致水槽底边宽度-1变短：
// 若向内移动短板，水槽的短板min(h[left],h[right])可能变大，底边宽度-1，下个水槽面积可能增大
// 若向内移动长板，水槽的短板min(h[left],h[right])不变或者变小，底边宽度-1，下个水槽面积一定变小
// 因此，初始化双指针分列水槽左右两端，循环每轮将短板向内移动一格，并更新面积最大值，直到两指针相遇即可

如果你感觉读后有收获，可以点击下方打赏请作者喝杯咖啡。