CONTENTS
- LeetCode 1. 两数之和
- LeetCode 2. 两数相加
- LeetCode 3. 无重复字符的最长子串
LeetCode 1. 两数之和
【题目描述】
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
【示例1】
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
【示例2】
输入：nums = [3,2,4], target = 6
输出：[1,2]
【示例3】
输入：nums = [3,3], target = 6
输出：[0,1]
【提示】
2 ≤ n u m s . l e n g t h ≤ 1 0 4 2\le nums.length\le 10^4 2≤nums.length≤104
− 1 0 9 ≤ n u m s [ i ] ≤ 1 0 9 -10^9\le nums[i]\le 10^9 −109≤nums[i]≤109
− 1 0 9 ≤ t a r g e t ≤ 1 0 9 -10^9\le target\le 10^9 −109≤target≤109
【分析】
维护一个哈希表，记录 n u m s [ 1 ] ∼ n u m s [ i − 1 ] nums[1]\sim nums[i-1] nums[1]∼nums[i−1]，当遍历到 n u m s [ i ] nums[i] nums[i] 时，通过哈希表查找是否存在 t a r g e t − n u m s [ i ] target-nums[i] target−nums[i]，如果存在说明找到答案。
【代码】
class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> st;for (int i = 0; i < nums.size(); i++){int x = target - nums[i];if (st.count(x)) return { st[x], i };st[nums[i]] = i;}return {}; // 为了防止编译出问题}
};
LeetCode 2. 两数相加
【题目描述】
给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 0 0 之外，这两个数都不会以 0 0 0 开头。
【示例1】
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
【示例2】
输入：l1 = [0], l2 = [0]
输出：[0]
【示例3】
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]
【提示】
每个链表中的节点数在范围 [ 1 , 100 ] [1, 100] [1,100] 内
0 ≤ N o d e . v a l ≤ 9 0\le Node.val\le 9 0≤Node.val≤9
题目数据保证列表表示的数字不含前导零
【分析】
模拟题，遍历两个链表，按照高精度加法的思想逐位相加，直到遍历完两个链表且没有进位即可。构造结果链表时可以先创建一个虚拟头结点，返回的时候返回虚拟头结点的下一个结点即可。
【代码】
/*** 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) {auto dummy = new ListNode(-1), cur = dummy; // 虚拟头结点，cur表示当前指向的结点int t = 0; // 进位while (l1 || l2 || t){if (l1) t += l1->val, l1 = l1->next;if (l2) t += l2->val, l2 = l2->next;cur = cur->next = new ListNode(t % 10); // 记得要更新cur指向下一个结点t /= 10;}return dummy->next;}
};
LeetCode 3. 无重复字符的最长子串
【题目描述】
给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。
【示例1】
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
【示例2】
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
【示例3】
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是子串的长度，"pwke" 是一个子序列，不是子串。
【提示】
0 ≤ s . l e n g t h ≤ 5 ∗ 1 0 4 0\le s.length\le 5*10^4 0≤s.length≤5∗104
s 由英文字母、数字、符号和空格组成
【分析】
我们枚举所有以 i i i 为尾端点的子串，分别找出最长的不包含重复字符的子串。因此对于每个 i i i，我们需要找到一个最靠左端点的 j j j，使得 j ∼ i j\sim i j∼i 中不包含重复的字符。现在再假设 i i i 向右移动到 i ′ i' i′，显然其对应的 j ′ j' j′ 一定大于等于 j j j，否则通过反证法， j ′ j' j′ 在 j j j 的左边且 j ′ ∼ i ′ j'\sim i' j′∼i′ 中不包含重复的字符，那么 j ′ ∼ i j'\sim i j′∼i 中一定也不包含重复的字符。
综上，我们在枚举 i i i 的时候同样也只需要枚举一遍 j j j，而不需要重复枚举。
【代码】
class Solution {
public:int lengthOfLongestSubstring(string s) {unordered_map<char, int> st;int res = 0;for (int i = 0, j = 0; i < s.size(); i++){st[s[i]]++;while (st[s[i]] > 1) st[s[j++]]--; // 当j==i时s[i]一定只出现一次了res = max(res, i - j + 1);}return res;}
};
