1. 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

示例 1：

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

示例 2：

1
2
输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

1
2
输入：nums = [3,3], target = 6
输出：[0,1]

提示：

  • 2 <= nums.length <= 104
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109
  • 只会存在一个有效答案

暴力方法，对于每一个 num，和 nums 中其他所有 num 计算 target 即可。

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

更高效率的方式是先将 nums 记录到一个哈希表中，遍历 num 时只需要在哈希表中查询 target - num。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution 
{
public:
    vector<int> twoSum(vector<int>& nums, int target) 
    {
        std::unordered_map<int, int> resMap;
        for(int i = 0; i < nums.size(); ++i)
        {
            resMap[nums[i]] = i;
        }

        for(int i = 0; i < nums.size(); ++i)
        {
            int val = target - nums[i];
            auto iter = resMap.find(val);
            if(iter != resMap.end() && i != iter->second)
            {
                return {i, iter->second};
            }
        }

        return {};
    }
};

以上写法的不足之处在于构建哈希表时额外多了一次遍历，实际上可以边计算结果边构建，在遍历到其中一个 num 时不需要急于得出结果，只将其放入哈希表，因为后续一定会遍历到 target - num。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution 
{
public:
    vector<int> twoSum(vector<int>& nums, int target) 
    {
       std::unordered_map<int, int> resMap;
       for(int i = 0; i < nums.size(); ++i)
       {
            if(resMap.count(target - nums[i]))
            {
                return {i, resMap[target - nums[i]]};
            }
            else
            {
                resMap[nums[i]] = i;
            }
       }
       return {};
    }
};

2. 反转链表

给定单链表的头节点 head ，请反转链表，并返回反转后的链表的头节点。

示例 1：

1
2
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

1
2
输入：head = [1,2]
输出：[2,1]

示例 3：

1
2
输入：head = []
输出：[]

提示：

  • 链表中节点的数目范围是 [0, 5000]
  • -5000 <= Node.val <= 5000

链表结构：

1
2
3
4
5
6
7
8
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) {}
};

定义一个 curNode 和一个指向 curNode 下一个节点的 nextNode，只需要将 nextNode 的 next 指针反向指向 curNode 即可。

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
class Solution 
{
public:
    ListNode* reverseList(ListNode* head) 
    {
        if(!head)
        {
            return nullptr;
        }

        ListNode* curNode = head;
        ListNode* nextNode = curNode->next;

        while(nextNode)
        {
            if(curNode == head)
            {
                curNode->next = nullptr;
            }

            ListNode* tmpNode = nextNode->next;

            nextNode->next = curNode;

            curNode = nextNode;

            nextNode = tmpNode;
        }

        return curNode;
    }
};

以上写法有一个瑕疵，我们在一个循环中增加了 curNode 是否为 head 的条件判断，会使得这个条件判断执行多次。为此，可以将 curNode 从 nullptr 开始定义，nextNode 定义为 head，这样就不需要在循环中处理特殊逻辑。

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
class Solution 
{
public:
    ListNode* reverseList(ListNode* head) 
    {
        if(!head)
        {
            return nullptr;
        }

        ListNode* curNode = nullptr;
        ListNode* nextNode = head;

        while(nextNode)
        {
            ListNode* tmpNode = nextNode->next;

            nextNode->next = curNode;

            curNode = nextNode;

            nextNode = tmpNode;
        }
        return curNode;
    }
};

3. 两数相加

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：

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

示例 2：

1
2
输入：l1 = [0], l2 = [0]
输出：[0]

示例 3：

1
2
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

提示：

  • 每个链表中的节点数在范围 [1, 100] 内
  • 0 <= Node.val <= 9
  • 题目数据保证列表表示的数字不含前导零

遍历两个链表，将每次迭代的结果求和放入新链表即可。注意两个链表的长度可能不一样，并且要处理进位问题。

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
class Solution 
{
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) 
    {
        if(!l1 || !l2)
        {
            return nullptr;
        }    

        ListNode* resHead = nullptr;
        ListNode* preNode = nullptr;
        bool isCarry = false;

        while(l1 || l2)
        {
            int curVal = 0;
            if(l1)
            {
                curVal += l1->val;
                l1 = l1->next;
            }

            if(l2)
            {
                curVal += l2->val;
                l2 = l2->next;
            }

            if(isCarry)
            {
                curVal += 1;
            }

            if(curVal >= 10)
            {
                isCarry = true;
            }
            else
            {
                isCarry = false;
            }
            curVal = curVal % 10;

            ListNode* tmpNode = new ListNode();
            tmpNode->val = curVal;

            if(!resHead)
            {
                resHead = tmpNode;
                preNode = resHead;
            }
            else
            {
                preNode->next = tmpNode;
                preNode = tmpNode;
            }
        }

        if(isCarry)
        {
            ListNode* tmpNode = new ListNode();
            tmpNode->val = 1;
            preNode->next = tmpNode;
        }

        return resHead;
    }
};

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

给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。

示例 1:

1
2
3
输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。注意 "bca" 和 "cab" 也是正确答案。

示例 2:

1
2
3
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

1
2
3
4
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
      请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

提示：

  • 0 <= s.length <= 5 * 104
  • s 由英文字母、数字、符号和空格组成

我们边遍历该字符串，边建立一个字符和索引的哈希表。同时维护一个最长子串长度 res 和当前子串长度 cur 以及当前子串的开始索引 curBeginIndex。如果哈希表中没有当前字符，则当前子串长度自增，并放入哈希表中。

如果哈希表中查到了当前字符，且当前索引要大于 curBeginIndex，则说明当前子串出现了重复。此时需要更新哈希表中的索引，当前子串的长度也求得为 i - oldIndex，当前子串的开始索引也需要更新为 oldIndex + 1。

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
class Solution 
{
public:
    int lengthOfLongestSubstring(string s) 
    {
        std::unordered_map<char, int> chMap;
        int res = 0, cur = 0, curBeginIndex = 0;
        for(int i = 0; i < s.size(); ++i)
        {
            if(chMap.count(s[i]) && chMap[s[i]] >= curBeginIndex)
            {
                int oldIndex = chMap[s[i]];
                chMap[s[i]] = i;
                cur = i - oldIndex;
                curBeginIndex = oldIndex + 1;
            }
            else
            {
                chMap[s[i]] = i;
                ++cur;
            }
            res = std::max(res, cur);
        }
        return res;
    }
};

这本质上是一种滑动窗口的思想，我们可以用一种更清晰的写法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution 
{
public:
    int lengthOfLongestSubstring(string s) 
    {
        std::unordered_map<char, int> chMap;
        int res = 0, left = 0;
        
        for(int right = 0; right < s.size(); ++right) 
        {
            if(chMap.count(s[right]) && chMap[s[right]] >= left) 
            {
                left = chMap[s[right]] + 1;
            }
            chMap[s[right]] = right;
            res = std::max(res, right - left + 1);
        }
        return res;
    }
};

注意到 std::max(res, right - left + 1) 这个写法，因为数组索引是从 0 开始的，所以计算长度的时候需要加1。比如 right 为 2，left 为 0 时，长度应该为3。left 和 right 框定的区域就是滑动窗口的区域，窗口向前滑动，left 和 right 按照一定规则变更，这就是滑动窗口的思想。