1.两数之和
描述:给定一个整数数组
nums
和一个目标值
target
,请你在该数组中找出和为目标值的那两个整数,并返回他们的数组下标。
暴力循环
没啥好说的,最容易想到的逻辑,时间复杂度O(n2)
双指针
排序后,利用双指针向中间逼近,知道找到目标值,时间复杂度O(nlogn)
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int left = 0, right = numbers.size() - 1;
while (left < right)
{
if (numbers[left] + numbers[right] < target)
left++;
else if (numbers[left] + numbers[right] > target)
right--;
else
return vector<int>{left + 1, right + 1};
}
return {};
}
};
一遍字典
对于当前元素x,与之匹配的另一数字为target-x,我们每遍历一个x,都将target-x作为key添加到字典中,其值为下标,在之后的遍历过程中,一旦发现当前x已存在字典中,说明之前已经找到匹配的元素,然后字典返回其下标。时间复杂度O(n)
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> ret = { -1, -1 };
map<int, int> m;
for (int i = 0; i < nums.size(); i++)
{
int pair = target - nums[i];
int x = m[pair];
if (m[pair])
{
ret[0] = m[pair] - 1; ret[1] = i;
return ret;
}
m[nums[i]] = i + 1;
}
return ret;
}
};
2.两数相加
描述:给出两个
非空
的链表用来表示两个非负的整数。其中,它们各自的位数是按照
逆序
的方式存储的,并且它们的每个节点只能存储
一位
数字。
这题熟悉链表的话还是很容易实现吧,稍微得注意下进位问题
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
int car = 0;
ListNode* res = NULL;
ListNode* p0 = res;
ListNode* p1 = l1;
ListNode* p2 = l2;
while (p1 != NULL && p2 != NULL)
{
if (!res)
{
res = new ListNode((p1->val + p2->val + car) % 10);
p0 = res;
}
else
{
p0->next = new ListNode((p1->val + p2->val + car) % 10);
p0 = p0->next;
}
if (p1->val + p2->val + car >= 10)
car = 1;
else
car = 0;
p1 = p1->next;
p2 = p2->next;
}
while (p1)
{
p0->next = new ListNode((p1->val + car) % 10);
if (p1->val + car >= 10)
car = 1;
else
car = 0;
p1 = p1->next;
p0 = p0->next;
}
while (p2)
{
p0->next = new ListNode((p2->val + car) % 10);
if (p2->val + car >= 10)
car = 1;
else
car = 0;
p2 = p2->next;
p0 = p0->next;
}
if (car == 1)
p0->next = new ListNode(1);
return res;
}
};
3.无重复字符的最长子串
描述:给定一个字符串,请你找出其中不含有重复字符的
最长子串
的长度。
解决该问题可以使用滑动窗口模型。我们维护一个滑动窗口,并限制其中的字符集不可重复,每次滑动窗口进行扩张,若出现重复则收缩窗口。在具体实现中,我们可以用两个下标来作为滑动窗口的边界,以一个字典来维护字符集。然后保存出现过的最大长度。
如何收缩窗口有两种策略,这与我们的字典有关。
若字典的值为bool型,即我们只关心该字符是否存在,则左边界每次向右收缩一个单位,每次收缩都去除掉某个字符,直到右边界扩张进的新字符没有出现过为止。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
map<int, int> m;
int left = 0, right = -1;
int res = 0;
for (int i = 0; i < s.length(); i++)
{
if (m[s[i]])
{
m[s[left]] = false;
left++;
i--;
continue;
}
right++;
m[s[i]] = true;
res = max(res, right - left + 1);
}
return res;
}
};
若字典的值为某个字符出现的下标,则我们每次收缩都收缩到该下标+1处。若这个下标比左边界小,则收缩到左边界+1
class Solution {
public:
int lengthOfLongestSubstring(string s) {
map<int, int> m;
int left = 0, right = 0;
int res = 0;
for (int i = 0; i < s.length(); i++)
{
if (m[s[i]] && m[s[i]] > left)
left = max(left + 1, m[s[i]]);
right = i;
m[s[i]] = i + 1;
res = max(res, right - left + 1